Основні правила комбінаторики
Розділ. Комбінаторика
Тема 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 квіток, можна скласти |