Формули комбінаторики

Основний принцип комбінаторики (правило множення). Нехай треба поcлідовно виконати k дій. Якщо першу можна виконати n ₁ способами, після чого другу — n ₂ способами, третю — n ₃ способами і т. д., то всі k дій може бути виконано способами.

Комбінації (сполуки) з n елементів по k. Нехай A — множина з n елементів. Довільна k -елементна підмножина множин з n елементів називається комбінацією з n елементів по k. Порядок елементів у підмножинах неістотний. Число k -елементних підмножин множини з n елементів позначають . Воно дорівнює:

де

Домовимось, що 0! =1, тоді

Справедливі властивості:

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

Різні впорядковані множини, які відрізняються тільки порядком елементів (тобто можуть бути утворені з тієї самої множини), називаються перестановками цієї множини. Число перестановок множини з n елементів дорівнює:

Розміщення з n елементів по k. Упорядковані k -елементні підмножини мно­жини, що містить n елементів, називаються розміщенням з n елементів по k. Число розміщень з n елементів по k дорівнює:

Біном Ньютона. де — натуральне число. Якщо то

Величина

є (k+ 1)-йчлен в розкладенні бінома,

Число способів розбиття множини з n елементів на m груп. Нехай k ₁, k ₂, …, k_m — цілі невід'ємні числа, причому k ₁ + k ₂ + …+ k_m = n. Число способів, якими можна подати множину A з n еле­ментів у вигляді суми n множин, що містять відповідно k ₁, k ₂, …, k_m елементів, дорівнює:

Перестановки з повтореннями. Число різних перестановок, які можна утворити з n елементів, серед яких є k ₁ елементів першого типу, k ₂ елементів другого типу,..., k_m елементів m -го типу, дорівнює: