Розділ. Комбінаторика
Тема 1. Перестановки. Розміщення. Комбінації
План
1. Основні правила комбінаторики.
2. Розміщення без повторень та з повтореннями.
3. Перестановки без повторень та з повтореннями. 4. Комбінації без повторень та з повтореннями.
Комбінаторика – це розділ математики про вибір і розміщення елементів деякої множини на основі якихось умов.
Основні правила комбінаторики
1. Нехай А 1, А 2 …Аn - скінченна множина скінченних множин, жодні дві з яких не мають спільних елементів. Тоді
1) Правило суми. 
Потужність об’єднання множин дорівнює сумі потужностей цих множин
- скорочений запис правила суми.
2) Правило добутку 
Наслідок
Якщо елемент 
можна вибрати n способами, а елемент 
- m способами, то
1) елемент 
можна вибрати m+n способами;
2) вибір пари 
можна здійснити 
способами.
2. Розміщенням з n елементів по k (познач. 
або 
) називається будь-яка упорядкована множина (задано порядок її елементів), складена з k елементів, вибраних із n - елементної множини. Якщо вибрані елементи не повторюються, то одержуємо розміщення без повторень, а якщо повторюються – то з повтореннями.
Розміщення без повторень – це такі набори елементів, які відрізняються або видом елементів, або порядком їх розміщення.
Наприклад, н ехай є множина 
Розміщення без повторень з 3-х по два: 
Розміщення з повторенням з 3-х по два: 
Формули для числа розміщень А 
| Без повторень | З повтореннями |
А =  або А = 
|  =n 
|
3. Перестановки – це розміщення з n елементів по n, що відмінні одне від одного порядком елементів, що в них входять (в перестановки входять всі елементи множини)
Наприклад, 
Перестановки без повторень: 
Формули для числа перестановок 
| Без повторень | З повтореннями |
P  =n!, де n!= 1 
(читається “ен факторіал”), 0!=1
|  , де 
|
Мультимножина – це множина, яка містить однакові елементи.
Якщо 
то можна записати 
4. Комбінаціями з n елементів по k (позначають 
або 
) називають всі можливі набори довжиною k, утворені з n - елементної множини, які відмінні одна від одної лише складом елементів (але не порядком).
Якщо маємо множину з n елементів різного виду і число елементів кожного виду необмежене, то набори довжиною k, які не залежать від порядку розміщення елементів, називаються комбінаціями з повторенням.
Наприклад, н ехай є множина 
. Якщо утворюємо комбінації без повторень з 3-х по 2, то дістанемо: 
;
якщо з повтореннями, то , .
Формули для числа комбінацій (сполучень) C
| Без повторень | З повтореннями |
C =  , С  =1
| 
|
Деякі властивості числа комбінацій (сполучень) без повторень
- С
(зокрема, С 
) - С
- С
Приклад 1. Кількість різних тризначних чисел, які можна скласти з цифр 1, 2, 3, 4, 5, 6, якщо цифри не можуть повторюватися, А  = 
Приклад 2. Кількість різних тризначних чисел, які можна скласти з чисел 1, 2, 3, 4, 5, 6, якщо цифри в числі можуть повторюватися,
 =6  =216
|
Приклад 3. Кількість різних шестизначних чисел, які можна скласти з цифр 1, 2, 3, 4, 5, 6, не повторюючи ці цифри в одному числі, дорівнює  =720
Приклад 4. Кількість різних шестизначних чисел, які можна скласти з трьох двійок, двох сімок і однієї п’ятірки 
(враховано, що 3+2+1=6)
|
Приклад 5. Із класу, що складається з 25 учнів, можна виділити 5 учнів для чергування по школі С  способами, тобто   способами
Приклад 6. Якщо у продажу є квіти чотирьох сортів, то різних букетів, що складаються з 7 квіток, можна скласти 
|
