1 2 / 6 2 3 4 5 6

Основні комбінаторні з'єднання без повторень елементів

Дата: 2025-06-02; Просмотры: 9

Оценка:

0.00 из 5.00 — оценок

Скачиваний: 0

З'єднання – прості комбінаторні конфігурації, до яких відносять:

– перестановки,

– сполучення,

– розміщення.

Перестановки

Перестановкою із n елементів або n-перестановкою називають упорядковану послідовність (кортеж, вектор) елементів множини.

Дві перестановки вважаються різними, якщо вони відрізняються порядком розташування елементів в них.

Наприклад.

Нехай є множина . Згенерувати усі перестановки елементів цієї множини. Перестановки: Перестановки згенеровані у порядку зростання натуральних чисел, поставлених у відповідність кожній з них.

Теорема 1

Примітка: визначимо 0! = 1.

Доведення.

Нехай є різних об'єктів (наприклад. куль з різними номерами) і їх необхідно розташувати на різних місць (комірок з різними номерами). На перше місце (або у першу комірку) можна розмістити будь-який із наявних елементів. Після цього, на друге місце можна розмістити будь-який із елемента, що лишилися. Зауважимо, що число претендентів на друге місце не залежить від того, який конкретно елемент був обраний на перше місце. Далі на 3 місце – претендента і так далі. На останнє місце залишиться один претендент. За правилом добутку маємо: .

Наприклад.

1) Скільки різних перестановок можна згенерувати із елементів множини

Розв’язання.

Кількість усіх перестановок у множині, що має 3 різні елементи дорівнює: .

2) Скільки різних слів можна утворити, переставляючи букви в слові "домбра"?

Розв’язання.

Оскільки усі літери у слові "домбра" різні та нас цікавить тільки порядок розташування цих літер, то

3) Трійка дівчат водять хоровод. Скількома способами вони можуть стати у коло?

Розв’язання.

Якщо дівчата стояли б на місці (кожне місце мало б номер), то вийшло б способів стати в коло. Але так, як дівчата водять хоровод, то їх розташування відносно оточення неважливе, а важливо, як вони розташовані одна відносно іншої. Тобто існують перестановки,що переходять одна в іншу. Наприклад, якщо взяти усі перестановки із 3 цифр, то їх можна розбити на 2 групи, причому у кожній із цих груп перестановки не відрізняються:

Тоді, кількість різних перестановок дівчат у хороводі дорівнює:

Розміщення

( - перестановки)

Розміщення із по – упорядкована послідовність із елементів множини, що містить всього елементів.

Два розміщення вважаються різними, якщо вони відрізняються:

– складом елементів;

– порядком розташування елементів;

– і тим, і другим.

Наприклад.

Нехай є множина

Згенерувати усі розміщення із 3 по 2. Розміщення із 3 по 2 для :

Два розміщення та – відрізняються порядком розташування елементів; та – відрізняються складом елементів; а та – і складом, і порядком розташування елементів.

Теорема 2

Примітка: при :

Доведення.

Нехай є різних об'єктів і їх необхідно розмістити на різних місць. На 1-е місце є претендентів, на 2-е – претендент, на третє – , ..., на -е місце – претендентів. За правилом добутку отримаємо, що кількість різних розміщень із по складає:

Наприклад.

1) Скількома способами можна розставити на полиці 5 книг із 7?

Розв’язання.

Оскільки усі книжки різні, то нас цікавить і які книжки будуть розставлені на полиці, і у якому порядку:

2) Скільки різних чотирьохлітерних ідентифікаторів можна отримати, використовуючи літери алфавіту , якщо ні одна із літер не повторюється?

Розв’язання.

У алфавіті всього 5 літер, 4 із них вони повинні бути використані для генерування ідентифікатору, причому порядок літер у ідентифікаторі має значення:

Сполучення

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

Різні сполучення відрізняються один від одного тільки складом елементів, але не їх порядком.

Наприклад.

Нехай є множина

Згенерувати усі сполучення із 3 по 2.

Сполучення із 3 по 2 для :

Теорема 3

Доведення.

Кожне сполучення із елементів можна упорядкувати способами, тобто з нього виходить перестановок. Для усіх сполучень маємо перестановок, але це число дорівнює кількості різних розміщень із елементів по , а отже, . Тоді, використовуючи теорему 2 маємо:

Властивості числа сполучень

2. Симетричність числа сполучень:

3. Правило Паскаля

Для числа сполучень із по справедливе наступне рекурентне співвідношення:

4. Біном Ньютона:

– біноміальні коефіцієнти.

При сума біноміальних коефіцієнтів дорівнює:

Наприклад.

1) Скількома способами із 25 членів наукового товариства можна обрати президію в кількості 3 осіб?

Розв’язання.

Оскільки треба обрати 3 осіб для роботи у президії наукового товариства, то порядок вибору значення не має, а має значення тільки, які особи із 25 наявних увійдуть у склад президії. Тоді, число способів обрати президію у складі із 3 осіб дорівнює: .

2) Скількома способами із 25 осіб наукового товариства можна обрати президента, віцепрезидента та вченого секретаря?

Розв’язання.

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

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

Третій варіант міркувань полягає у застосуванні тільки правила добутку. Президент наукового товариства може бути обраний способами. Після цього і незалежно від цього, віцепрезидент може бути обраний вже способами. Відповідно, секретар, способами. За правилом добутку маємо: .

2. На книжковій полиці розміщується томів книг. Скількома способами можна розставити їх так, щоб та томи не стояли поряд?

Розв’язання.

Задача легше розв’язується через зворотну задачу. 30 томів книг можна розставити на полиці без будь-яких обмежень способами. Обчислимо число способів розставити книжки так, що й том будуть стояти поряд. Перший та другий том можна поставити поряд способами ( або ). Далі маємо розставити на полиці окремих томів та один складний об'єкт, що складається із та томів: .

За правилом добутку маємо рішення зворотної задачі: .

Тоді, пряма задача має наступний розв’язок:

3. Чотири стрілка повинні вразити 8 мішеней (кожен по 2). Скількома способами вони можуть розподілити мішені між собою?

Розв’язання.

Для кожного стрілка має значення, які мішені йому будуть розподілені, але не має значення у якому порядку він буде в них стріляти. Тому, число варіантів вибору двох мішеней із 8 для першого стрілка дорівнює , для другого – , для третього відповідно – , для останнього – . За правилом добутку: .

4. Колода у карт містить 4 масті по карт у кожній.

Скількома способами можна вибрати:

1) 5 карт, 4 з яких з однаковими номерами?

2) три карти з одними номерами та 2 з іншими однаковими номерами?

Розв’язання.

1) Для того, щоб вибрати 4 карти із одним номером достатньо із наявних номерів вибрати один, а останню, 5 карту вибрати із колоди без 4 карт із цим номером: .

2) Для того, щоб вибрати 3 карти із одним номером треба спочатку вибрати один номер із існуючих, а потім із 4 карт з таким номером вибрати три карти: . Аналогічно вибираємо дві карти з однаковими номерами: , але номер вибираємо із варіанту.