Тема 6. Комбінаторні об'єкти, правила суми і добутку.

Комбінаторні об'єкти, правила суми і добутку.

Питання теми

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

2. Правила суми і добутку.

Основні терміни теми : комбінаторика, правило суми, правило добутку.

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

На практиці часто зустрічаються задачі, в яких необхідно підрахувати число всіх можливих способів розміщення деяких предметів скінченної множини або число всіх можливих способів виконання певної дії із скінченної множини таких дій. Наприклад, скількома різними способами можна розставити дужки у виразі a + b + c + d + e + f, якщо операція + асоціативна, а букви a, b, c, d, е, f- деякі дійсні числа? Скількома способами можуть розподіли¬тися медалі на чемпіонаті світу з футболу серед 16-ти команд-учасниць фінальної групи? Задачі такого типу називаються комбі¬наторними, а методи їх розв'язку - методами комбінаторного аналізу. Оскільки комбінаторика має справу зі скінченними мно¬жинами, то її часто називають теорією скінченних множин.

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

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

2. Правила суми і добутку.

Правило суми: якщо об’єкт а може бути вибраний р способами, а об’єкт b-іншими q способами, тоді вибір “а або b” може бути здійсненний p + q способами. Слід мати на увазі, що вибори а або b тут є взаємно виключними.

Правило добутку: якщо об’єкт а може бути вибраний р способами та після кожного з таких виборів об’єкт b в свою чергу може бути вибраний q способами, тоді вибір “а або b” у вказаному порядку можна здійснити pq способами. Це правило використовують у тих випадках, коли вибори a та b незалежні.

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

Дано скінченні множини  А і В, причому АВ=. Позначимо кількість елементів множин А і В через n(A) і n(B), а кількість елементів їхнього об’єднання - n(AB). Оскільки множини А і В не мають спільних елементів, тоді:

n(AB) = n(A) + n(B).

Це правило суми. Його можна узагальнити на випадок m множин, які попарно не перетинаються:

 ,

якщо  для всіх ij.

Якщо множини перетинаються, то

n(A  B) = n(A) + n(B) - n(A  B).

Звідси:

n(A  B) = n(A) +n(B) - n(A  B) .

Для трьох множин:

n(A  B  C) = n(A) + n(B) + n(C) - n(A  C)-

-n(A  B) - n(B  C) + n (A  B  C).

Для m множин:

 

- 

...

Приклади.

1. На першому курсі педагогічного факультету 95 студентів захоплюються спортом. З них 50 займаються волейболом, 48 - баскетболом, 36 - тенісом, волейболом і баскетболом - 21, волейболом і тенісом - 15, баскетболом і тенісом -18. Скільки студентів займаються іншими видами спорту, якщо 5 студентів займаються баскетболом, волейболом і тенісом?

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

Позначимо через В - множину студентів, які займаються волейболом, Б - баскетболом і Т - тенісом. Ці три множини за умовою перетинаються. За правилами суми визначимо, скільки студентів займаються хоча б одним з цих трьох видів спорту : n(ВБТ) = n(В) + n(Б) + n(Т) - n(ВТ) - n(ВБ) - n(БТ)+ n(ВБТ) = 50+48+36-15-18-21+5=85 (студентів).

Тоді іншими видами спорту займаються: 95-85=10 (cтудентів).

2. Скільки всього чотирицифрових чисел у десятковій системі числення?

Розв’язання. Будь-яке чотирицифрове число можна розглядати як кортеж довжини вигляду (а1, a2, a3, a4), де

a1 A2= { 1, 2, 3, 4, 5, 6, 7, 8, 9 },

a2A2= { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }, a3 A2 i a4  A2.

Тоді множина всіх чотирицифрових чисел є декартів добуток  . Число елементів цієї множини

 .