Основні правила комбінаторики

Розділ. Комбінаторика

Тема 1. Перестановки. Розміщення. Комбінації

План

1. Основні правила комбінаторики.

2. Розміщення без повторень та з повтореннями.

3. Перестановки без повторень та з повтореннями. 4. Комбінації без повторень та з повтореннями.

Комбінаторика – це розділ математики про вибір і розміщення елементів деякої множини на основі якихось умов.

Основні правила комбінаторики

1. Нехай А _1, А ₂ …А_{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. С (зокрема, С )
2. С
3. С

Приклад 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 квіток, можна скласти