Комбінаторний аналіз

• Логічний  спосіб

     Основний  принцип комбінаторики:Нехай послідовно можна виконати  дій. Першу дію можна  виконати n 1    способами, а другу - n 2 способами.Тоді  всі  дій  послідовно можна виконати .

     Правило додавання. Якщо дві взаємовиключні дії можуть бути виконані відповідно n1 та n2 способами, тоді якусь одну з цих дій можна виконати:

n 1 + n 2 способами.[6]

Приклад : З міста А в місто В можна добратися 4 потягами, 2 літаками, 6

автобусами. Скількома способами можна добратися з міста А у місто В.

Розв’язання. Проїзд з А у В на потягу, літаку або автобусом є взаємови-

ключними операціями, тому загальну кількість маршрутів можна одержати як суму способів пересування, тобто N = + = 4+ 2 +6 =12 способів. 

     Правило множення. Нехай дві виконувані одна за одною дії можуть бути здійснені відповідно n1 та n2 способами. Тоді обидві вони можуть бути виконані   n 1 ・ n 2 способами.[6]

Приклади:

1.У чемпіонаті країни з футболу беруть участь 16 команд. Скіль-

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

Розв’язання. N = × = 16 × 15 × 14= 3360.

2. Скільки сигналів можна подати з корабля за допомогою чоти-

рьох прапорів різного кольору, розміщуючи їх на щоглі, якщо використовувати різну кількість прапорів?

Розв’язання. Сигнали можна подавати чотирма, трьома, двома і одним

прапорами. Відповідно до правила множення, кількість можливих способів подачі сигналу з 4 прапорів складе = 4 × 3 × 2 × 1 =24 для сигналу з 3 прапорів =4 × 3  × 2 =24 способів, для сигналу з 2 прапорів маємо

  =4 × 3 =12

для сигналу з 1 прапора =4 способа. Загальну кількість сигналів можна одержати як суму способів для сигналів з 4, 3, 2 і 1 прапорів, тобто

N = + =24 + 24+ 12+4 = 60 способами.

Обидва правила узагальнюються на випадок будь−якої скінченної кількості дій. 

2.2  За допомогою формул  комбінаторики

  Множина́ — одне з основних понять сучасної математики. Строго воно не визначається, але може бути дано інтуїтивне визначення множини як сукупності певних і різних об'єктів довільної природи, яка розглядається як одне ціле. Об'єкти, які складають множину, називаються її елементами. Наприклад, можна говорити про множину усіх книг в певній бібліотеці, множину літер українського алфавіту або про множину всіх коренів певного рівняння тощо.

   Якщо X та Y — множини та будь-який елемент із X є також елементом із Y, то говорять, що:

• X є підмножиною (частиною) Y, позначення — X ⊆ Y;
• Y — надмножина (охоплююча множина) X, позначення — Y ⊇ X.

   У комбінаториці розрізняють три види різних з'єднань (комбінацій) елеме-

нтів фіксованої множини: перестановки, розміщення, сполучення.[3]

     Перестановками з елементів називають різні скінченні впорядковані множини(тобто такі множини,для яких указано порядок розміщення їх елементів),що їх можна дістати з деякої множини, яка містить елементів. Якщо всі елементи даної множини різні, дістаємо перестановки без повторень,  а якщо елементи можуть повторюватися, то перестановки з повтореннями:                                                                                          

Без повторень:                                                                                                      [6]

Приклад :Скільки різних тризначних чисел можна скласти за допомогою

трьох карток з цифрами 1, 2, 3?

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

Розв’язання. Загальна кількість можливих тризначних чисел дорівнює 

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

З повтореннями : 

Приклад:Кількість різних шестицифрових чисел, які можна скласти з трьох двійок, двох сімок і однієї п’ятірки: 
 

     Розміщенням  з  елементів по по k називають будь яку впорядковану множину з k елементів, складену з елементів даної множини , яка містить елементів.(Якщо вибрані елементи не повторюються, то одержуємо розміщення  без повторень, а якщо повторюються  ,то розміщення з повтореннями.)

Без повторень: 

Приклад:

Скільки різних двозначних чисел можна скласти за допомогою трьох карток

з цифрами 1, 2, 3?

Розв’язання: Загальна кількість можливих двозначних чисел визначається

відповідно до виразу :

 

З повтореннями: 

Приклад:Кількість різних трицифрових чисел, які можна скласти з цифр 1, 2, 3, 4, 5, 6, якщо цифри в числі можуть повторюватися: 
 

Комбінації( сполучення):

Без повторень :

     Комбінації( сполучення) без повторень з  елементів по називають будь-яку - елементну підмножину –елементної множини. 

При цьому: ; =; 

Приклад: Скількома способами можна вибрати дві цифри з трьох 1, 2, 3?

Розв’язання: Загальна кількість можливих способів вибору цифр дорівнює 

З повтореннями:

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

[9]

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

2.3  Метод перебору

Задача 1. Скільки двозначних чисел можна скласти, використовуючи цифри 1, 4 і 7?

Розв’язання . Для того щоб не пропустити і не повторити жодного з чисел, будемо выписувати їх у порядку зростання. Спочатку запишемо числа, які починаються з цифри 1, потім з цифри 4 і, нарешті, з цифри 7. Отримуємо наступний розклад.

Таким чином, з трох даних цифр можна скласти всього 9 різних двозначних чисел.

Однако  існує єдиний підхід к розв’язанню найрізноманітніших комбінаторних задач за допомогою складання спеціальних схем. Зовнішньо така схема нагадує дерево, звідси назва – дерево можливих  варіантів.  При правильній побудові дерева жоден  з варіантів розв’язання не буде втрачений.[7]

Повернемося до задачі про складання двозначних чисел з цифр 1, 4і 7. Для ії розв’язання можно побудувати  спеціальну схему.(9)

Ця  схема дійсно схожа на дерево, правда, "вверх ногами" і без стовбура. Знак “*” зображає корень дерева, вітки дерева – різноманітні варіанти розв’язання. Щоб отримати двозначне число, необхідно спочатку вибрати першу його цифру, а для неї є три варианта: 1, 4 або 7. Тому з точки * проведено три відрізка і на кінцівках поставлені цифри 1, 4 і 7.

Тепер потрібно вибрати другу цифру, а для цього також існує три варіанти: 1, 4 або 7. Тому від кожної першої цифри проведено по три відрізки, на кінцях яких знову записано 1, 4 або 7. Отже, отримано всьго 9 різних двозначних чисел. Інших двозначних чисел из цих трьох цифр скласти неможливо.

У наслідку, ми побачимо, як побудова дерева допомагає розв’язати найрізноманітніші комбінаторні задачі.

Додаткова під задача: Скільки двозначних чисел можна скласти, використовуючи цифри 1, 4 і 7, якщо цифри десятків і одиниць не повторюються? (15)

Задача 2. Скільки тризначних чисел можна скласти, використовуючи цифри 3 і 5?(8)

Задача 3. Туристична фірма планує відвідування туристами в Італии трьох міст: Венеції, Риму и Флоренції. Скільки існує варіантів такого маршрута?

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

Позначимо міста їх першими літерами. Тоді код кожного маршруту буде складатися з трьох букв: В, Р і Ф, кожна з яких повинна бути використана тільки один раз, наприклад, ВФР або ФРВ.(6)

 
 

Розв’язання задач[5]

1. Андрій зайшов у магазин, щоб купити майки. В магазині виявилися майки чотирьох кольорів: білі, голубі, зелені, чорні.

а) Скільки варіантів покупки є у Андрія, якщо він хоче купити дві майки?(7)

Підказка: позначте кольора майок Б, Г, З, Ч. Запишіть всі можливі варіанти покупки, виконуючи їх перебір в алфавітному порядку.

б) Скільки вариантів покупки є у Андрія, якщо він хоче купувати дві майки різного кольору?(6)

2. У турнірі з настольного тенісу приймали участь 5 чоловік.

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

Дайте відповідь на питання, використовуючи спосіб кодування, позначивши учасників турниру цифрами 1, 2, ....

3. У шостому класі вивчається 8 предметів. Скільки різних варіантів  розкладу можна скласти на понеділок, якщо у цей день повинно бути 5 уроків і всі різні?

Підказка: на першому уроці можна провести будь-який з 8 предметів, на другом уроці – будь-який з залишившихся 7 предметів, на третьому уроці …

4. У магазині є чотири  типи диваних подушок: круглі, овальні, прямокутні и трикутні Скільки варіантів покупки є у покупця, який хоче купити дві подушки?

Розв’яжить  задачу, закінчивши побудову дерева можливих варіантів.