Основні комбінаторні формули.

Нехай задана скінчена множина з n елементів

Означення. Довільна k – елементна підмножина множини з n елементів називається сполученням з n елементів по k. Порядок елементів у підмножині не є суттєвим.

Число сполучень з n елементів по k позначають , і визначають за формулою

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

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

Число перестановок P_n множини, що містить n елементів

Означення. Упорядковані k-елементні підмножини множини з n елементів називаються розміщеннями з n елементів по k. Різні розміщення з n елементів по k відрізняються або елементами, або їх порядком.

Число розміщень з n елементів по k позначається через , і визначають за формулою