Тема3. Комбінаторний аналіз

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

- скінченна множина, яка складається з елементів. Тоді говорять, що об’єкт з може бути вибран способами, та пишуть .

- множини, які попарно не пересікаються, тобто Æ при . Тоді, цілком природно, виконується рівність

.

У комбінаториці цей факт називається правилом суми. Для воно формулюється слідуючим чином: якщо об’єкт може бути вибран способами, а об’єкт - іншими способами, то вибір „або , або ” може бути здійснен способами.

Також у комбінаториці часто використовують правило добутку. Якщо об’єкт може бути вибран способами і після кожного з таких виборів об’єкт в свою чергу може бути вибран способами, то вибір впорядкованої пари може бути здійснен способами.

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

У вибірках можуть допускатися або не допускатися повторення елементів. Впорядкована -вибірка, у якої елементи можуть повторюватися, називається -розміщенням з повтореннями. Якщо елементи впорядкованої -вибірки попарно різні, то її називають -розміщенням без повторень або просто -розміщенням.

Будемо, крім того, -розміщення без повторень називати перестановками множини . Невпорядкована -вибірка, де елементи можуть повторюватися, називається -сполученнями з повтореннями. Якщо елементи впорядкованої -вибірки попарно різні, то її називають -сполученням без повторень або просто -сполученням. Будь-яке -сполучення можна розглядати як -елементну підмножину -елементної множини.

Приклад.

1) розміщення з повтореннями;

2) розміщення;

3) сполучення з повтореннями;

4) сполучення.

Число -розміщень з повтореннями позначимо через а без повторень – через Число перестановок -елементної множини позначимо через (тобто ). Число сполучень - сполучень з повтореннями позначимо через , а без повторень – через .

Утвердження 1.

Надалі для більшої спільності формул будемо вважати, що

Утвердження 2. при та при

Наслідок.

Утверждення 3. при та при

Утвердження 4.

Утвердження 5. Тоді число усіх ін’єктивних відображень вида дорівнює

Приклад. Скільки існує способів для розфарбування квадрату, який розділен на чотири частини (див.малюнок), з допомогою п’яти кольорів:

а) якщо допустити фарбування різних частин в один колір;

б) різні частини фарбуються в різні кольори.

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

Будемо розглядати кожне розфарбування як функціональне відображення множини номерів частей квадрата у множину кольорів , де Тоді, користуючись твердженнями 5 та 6, маємо:

а) б)

Приклад. Скільки способів існує, щоб вибрати 5 номерів з 36?

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

Нас цікавить кількість невпорядкованих -вибірок без повторень, тобто -сполучень. Використовуя утвердження 3, отримаємо, що потрібне число способів дорівнює

Приклад. У кількох випадках при виборі з колоди, яка містить 52 карти, 10 карт серед них виявляться усі 4 туза?

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

Виключив з розглядання тузи, отримаємо, що вибираються 6 карт з 48, а такий вибір можна здійснити способами:

Приклад. Маємо 30 монет номіналом 1, 2 та 3 копійки. Скільки існує різних комбінацій монет (наприклад, 3 монети по 1 копійці, 17 – по 2 копійці, 10 – по 3 копійці)?

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

За умовами задачі необхідно визначити кількість невпорядкованих виборок з повтореннями обсягу 30 з множини обсягу 3, тобто число -сполучень з повтореннями. Використовуя утвердження 4, отримуємо, що шукане число дорівнює

Приклад. Виведемо формулу для кількості цілочисленних розв’язань системи

(1)

де - цілі числа.

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

, , (2)

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

.

Якщо ж , то множина цілочисленних розв’язань системи (1) є порожньою, і кількість розв’язань у цьому випадку дорівнює 0.

Підрахуємо число розбивань скінченної множини , де на підмножин таких, що кожне містить елементів, тобто

Æ при .

Зрозуміло, що при цьому Зауважимо, що для деяких номерів можливо Æ. Число вказаних розбивань при фіксованих позначимо через .

Зауваження. У даному випадку набір підмножин множини в розбиванні є впорядкованим (тобто -впорядкована послідовність множин). Нижче, крім того, розглядається випадок, коли набір підмножин в розбиванні не є впорядкованим.

Утвердження 7. .

Утвердження 8. Число , де , дорівнює числу розміщень з повтореннями, серед елементів яких міститься елементів 1-го типу, елементів 2-го типу,..., елементів -го типу.

Кожному розміщенню вказаного типу поставимо у відповідність розбивання множини номерів елементів у вибірці на підмножини , де - множина номерів елементів -го типу у вибірці. Зрозуміло, що при цьому виконуються умови:

Æ при ,

Вказана відповідність між розміщеннями заданого типу і розбиваннями, які вдовольняють цим умовам, є взаїмно однозначним, звідки в силу твердження 7 і витікає справедливість твердження, що доказується.

Приклад. У студентській групі, яка складається з 25 людей, при виборі старости за висунуту кандидатуру проголосовали 12 студентів, проти – 10, утримались – 3. Кількома способами може бути проведено це голосування?

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

- множина студентів в групі;

- множина студентів, які проголосували за висунуту кандидатуру;

- множина студентів, які проголосували проти;

- множина студентів, які утримались від голосування.

Тоді Æ при , отже, шукане число дорівнює

Приклад. Кількома способами можна розфарбувати квадрат, який поділен на дев’ять частин, чотирьма кольорами таким чином, щоб у перший колір були розфарбовані 3 частини, у другий – 3, у четвертий – 1?

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

- множина кольорів, де . Тоді кожне розфарбування, яке розглядається як послідовність кольорів, в які фарбуються пронумеровані частини квадрата є впорядкованою виборкою з повтореннями обсягу 9 з множини тобто -розміщення з повтореннями. При цьому нас цікавлять розміщення з заданою комбінацією елементів (3 елемента – перший колір, 2 – другий, 3 – третій, 1 – четвертий). Но тоді, використовуя утвердження 8, отримуємо, що шукане число дорівнює

Підрахуємо тепер кількома способами можна розбити множину , де , на підмножини, серед яких для кожного є підмножин з елементами, де . При цьому на відміну від розглянутого раніш випадку у нашому випадку набір підмножин у розбиванні не є впорядкованим (тобто порядок підмножин в розбиванні не є істотним). Так, наприклад, розбивання множини вида

вважаються однаковими. Позначимо число невпорядкованих розбивань множини через

Утвердження 9. .

Приклад. Кількома способами з групи в 25 людей можна сформувати 5 коаліцій по 5 людей?

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

- множина людей у групі, - число коаліцій по людей, де Тоді за умовами задачі \ , отже шукане число буде дорівнювати де в силу утвердження 9

.

Поиск по сайту: