|
Основне правило комбінаторики
Нехай необхідно виконати послідовно k дій. Якщо першу дію можна виконати n1 способами, другу - n2 способами і так далі до k-ї дії, яку можна виконати nk способами, то всі k дій можна виконати n1 · n2 · ... · nk способами.
Приклад 1.
Скількома способами на першості світу з футболу можуть розподілитися медалі, якщо у фінальній частині грають 24 команди?
Розв'язок. Золоту медаль може одержати будь-яка з 24-х команд, тобто 24 можливості. Срібну медаль може виграти одна з 23-х команд, а бронзову - одна з 22-х команд. За основним правилом комбінаторики загальне число способів розподілу медалей 24 · 23 · 22 = 12144.
Скорочення n!=1 · 2 · 3 · ... · (n-1) · n називається факторіалом числа n (читається n-факторіал).
Упорядковані множини, які відрізняються одна від одної лише порядком своїх елементів (тобто можуть бути одержані з однієї і тієї ж множини лише перестановкою своїх елементів), називаються перестановками. Позначимо число всіх перестановок n-елементної множини Pn.
Приклад 2.
Скількома різними способами можна розмістити п'ять книжок на книжковій полиці?
Розв'язок. Шукане число розміщень є числом способів упорядкування множини з п'яти елементів. Значить, це число дорівнює P5 = 1 · 2 · 3 · 4 · 5 = 120.
Число різних m-елементних підмножин n-елементної множини становить
Число Cnm називається числом комбінацій або сполучень із n елементів по m елементів.
Кількість упорядкованих m-елементних підмножин n-елементної множини, всі m елементів якої різні, становить
Приклад 3.
Скількома різними способами можна розмістити п'ять учнів в аудиторії, яка має 20 місць?
Розв'язок. Шукане число способів дорівнює числу розміщень із 20 елементів, по 5 елементів, тобто A205 = 16 · 17 · 18 · 19 · 20 = 1860480.
Кількість різних комбінацій із n елементів по m елементів з повтореннями становить
Біном Ньютона
Рівність (a + b)n = Cn0 an b0 + Cn1 an-1 b1 + Cn2 an-2 b2 + ... + Cnn a0 bn називають біномом Ньютона.
Біноміальні коефіцієнти можна виписати у вигляді трикутної таблиці, яка носить назву трикутника Паскаля:
| | | | | 1 | | 1 | | | | |
| | | | 1 | | 2 | | 1 | | | |
| | | 1 | | 3 | | 3 | | 1 | | |
| | 1 | | 4 | | 6 | | 4 | | 1 | |
| 1 | | 5 | | 10 | | 10 | | 5 | | 1 |
У n-му рядку трикутника Паскаля стоять коефіцієнти розкладу (Cnk) з бінома Ньютона, причому кожний коефіцієнт, крім двох крайніх, які дорівнюють 1, — це сума відповідних коефіцієнтів із попереднього рядка.
Основні властивості біноміальних коефіцієнтів
-
Формула симетрії
-
Формула додавання
-
Формула суми всіх біноміальних коефіцієнтів
-
Формула винесення за дужки
Наверх |