ГоловнаАлгебраКомбінаторика

Комбінаторика

Основне правило комбінаторики

Нехай необхідно виконати послідовно \(k\) дій. Якщо першу дію можна виконати \(n_1\) способами, другу — \(n_2\) способами і так далі до \(k\)-ї дії, яку можна виконати \(n_k\) способами, то всі \(k\) дій можна виконати \(n_1 ~ \cdot ~ n_2 ~ \cdot ~ ... ~ \cdot ~ n_k \) способами.

Приклад 1.

Скількома способами на першості світу з футболу можуть розподілитися медалі, якщо у фінальній частині грають 24 команди?

Розв'язок. Золоту медаль може одержати будь-яка з 24-х команд, тобто 24 можливості. Срібну медаль може виграти одна з 23-х команд, а бронзову — одна з 22-х команд. За основним правилом комбінаторики загальне число способів розподілу медалей 24 · 23 · 22 = 12144.

Скорочення \(n! = 1 ~ \cdot ~ 2 ~ \cdot ~ 3 ~ \cdot ~ ... ~ \cdot ~ (n-1) ~ \cdot ~ n\) називається факторіалом числа \(n\) (читається \(n\)-факторіал).

Упорядковані множини, які відрізняються одна від одної лише порядком своїх елементів (тобто можуть бути одержані з однієї і тієї ж множини лише перестановкою своїх елементів), називаються перестановками. Позначимо число всіх перестановок \(n\)-елементної множини \(P_n\).

\[P_n=1 ~ \cdot ~ 2 ~ \cdot ~ ... ~ \cdot ~ (n-1) ~ \cdot n = n!\]

Приклад 2.

Скількома різними способами можна розмістити п'ять книжок на книжковій полиці?

Розв'язок. Шукане число розміщень є числом способів упорядкування множини з п'яти елементів. Значить, це число дорівнює P5 = 1 · 2 · 3 · 4 · 5 = 120.

Обчислення \(n\)-факторіала

\[n! = 1 ~ \cdot ~ 2 ~ \cdot ~ ... ~ \cdot ~ (n-1) ~ \cdot ~ n\]
\(n!\) \(=\) \(!\)

Число різних \(m\)-елементних підмножин \(n\)-елементної множини становить

\[C_{n}^{m}=\frac{n!}{m! ~ (n-m)!}\]
\[C_{n}^{0} = 1\]

Число \(C_{n}^{m}\) називається числом комбінацій або сполучень із \(n\) елементів по \(m\) елементів.

Число комбінацій із \(n\) елементів по \(m\) елементів

\[C_{n}^{m}=\frac{n!}{m! ~ (n-m)!}\]
\(m\) =
\(n\) =
\(C_n^m\)

Кожна впорядкована підмножина, яка містить \(m\) елементів даної множини з \(n\) елементів, називається розміщенням із \(n\) по \(m\) елементів. Таким чином, два різних розміщення із даних \(n\) елементів по \(m\) відрізняються один від одного або складом елементів, або порядком їх розміщення.

Кількість упорядкованих \(m\)-елементних підмножин \(n\)-елементної множини, всі \(m\) елементів якої різні, становить

\[A_{n}^{m} = P_{m} \cdot C_{n}^{m} = \frac{n!}{(n-m)!}\]

Число розміщень із \(n\) по \(m\) елементів

\[A_{n}^{m} = \frac{n!}{(n-m)!}\]
\(m\) =
\(n\) =
\(A_n^m\)

Приклад 3.

Скількома різними способами можна розмістити п'ять учнів в аудиторії, яка має 20 місць?

Розв'язок. Шукане число способів дорівнює числу розміщень із 20 елементів, по 5 елементів, тобто \(A_{20}^{5}\) = 16 · 17 · 18 · 19 · 20 = 1860480.

Кількість різних комбінацій із \(n\) елементів по \(m\) елементів з повтореннями становить

\[C_{n+m-1}^{n-1}=C_{n+m-1}^{m}\]

Біном Ньютона

Рівність \((a + b)^n = C_n^0 ~ a^n ~ b^0 + C_n^1 ~ a^{n-1} ~ b^1 + C_n^2 ~ a^{n-2} ~ b^2 ~ + ~ ... ~ + ~ C_n^n ~ a^0 ~ b^n\) називають біномом Ньютона.

Біноміальні коефіцієнти можна виписати у вигляді трикутної таблиці, яка носить назву трикутника Паскаля:

    1 1    
   1 2 1   
  1 3 3 1  
 1 4 6 4 1 
1 5 10 10 5 1

У \(n\)-му рядку трикутника Паскаля стоять коефіцієнти розкладу \(\big(C_n^k\big)\) з бінома Ньютона, причому кожний коефіцієнт, крім двох крайніх, які дорівнюють 1, — це сума відповідних коефіцієнтів із попереднього рядка.

Основні властивості біноміальних коефіцієнтів

  1. Формула симетрії

    \[C_{n}^{m}=C_{n}^{n-m}\]

  2. Формула додавання

    \[C_{n}^{m}+C_{n}^{m+1}=C_{n+1}^{m+1}\]

  3. Формула суми всіх біноміальних коефіцієнтів

    \[\sum_{k=0}^{n} {C_{n}^{k}}=2^n\]

  4. Формула винесення за дужки

    \[C_{n}^{k}=\frac{n}{k} \cdot C_{n-1}^{k-1}\]

Популярні статті