Комбінації. Комбінації з повтореннями

У тих випадках, коли нас не цікавить порядок елементів у розміщення, а лише його склад, вводять поняття комбінації..

Означення 5.1.6. Нехай , тобто множина складається з елементів, . Комбінацією без повторень з елементів по називають довільну k- підмножину множини , всі елементи якої різні.

Кількість різних комбінацій з елементів по без повторень позначають:

.

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

Теорема 5.1.6. Для довільних натуральних чисел і має місце формула:

.

Теорема 5.1.7. Для виконується рівність:

.

Доведення

Серед розміщень з елементів по можна виділити класи впорядкованих k-множин, які відрізняються лише порядком розміщення одних і тих самих елементів. У кожному класі таких множин буде , а кількість різних класів – . Отже, .<

Приклад. Скільки діагоналей у правильному п-кутнику?