Комбінації. 
Елементи комбінаторики

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

З одного елемента можна утворити тільки одну комбінацію. З двох елементів, а і bможна утворити дві комбінації по одному елементу і тільки одну комбінацію з двох елементів.

З трьох елементів a, b, cможна утворити такі комбінації: {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.

Комбінації з п елементів даної множини по kможна також розглядати як розміщення з п елементів по k, які відрізняються принаймні одним елементом. Виникає запитання, як визначити кількість комбінацій з n елементів по k. Число комбінацій з п по kпозначається С^k _n. Доведемо, що.

. (1).

Розглянемо множину, яка складається з п елементів, і комбінації, які складаються з kелементів. Всього комбінацій С^k _n. Якщо з кожної такої комбінації утворити всі можливі перестановки (їх буде Р_k = k!), то дістанемо всі можливі розміщення з п елементів по к, тобто число А^k _n. Отже, А^k _n = Р_k *С^k _n, (2).

Звідки.

Зауважимо, що за означенням покладають 0! = 1. Тому неважко помітити, що С¹ ₁ =1і Сⁿ _n = 1.

Приклад. Збори з 30 осіб вибирають трьох делегатів на конференцію. Скількома способами це можна зробити?

Із множини у 30 осіб треба вибрати підмножину з трьох осіб. Цеможна зробити способами .