Комбiнаторнi задачі. Правила суми i добутку.

1. Розглядаючи множини та операції над ними ми вказували, що порядок розміщення елементів немає значення, але є галузь математики, для якої порядок розміщення елементів множини має суттєве значення. Ця галузь математики називається комбінаторикою та розглядає задачі, пов’язані з розташуванням за певними правилами елементів скінченних множин i відшукання числа способів, якими це можна зробити. Такі задачі називаються комбінаторними. Наприклад: 1) скільки карточок спортлото потрібно купити, щоб точно вгадати 6 номерів? 2) скількома способами можна призначити в групі трьох чергових?; 3) скількома способами можна витягнути з колоди три карти, щоб набрати 21 очко?

Комбінаторика виникла з необхідності створення теорії азартних ігор. Найбільший вклад в її розвиток внесли П.Ферма, Б.Паскаль, Х.Гюйгенс, В.Лейбнiц, Я.Бернуллi. Значний інтерес до комбінаторики поновлюється в 50-х роках XX ст. у зв’язку з бурхливим розвитком кібернетики та дискретної математики i широким використанням електронно-обчислювальної техніки. Дуже широко використовується комбінаторика в теорії оптимального управління.

В комбінаториці є правила, які дозволяють елементарними способами розв’язати значну кількість комбінаторних задач. Розглянемо дві скінченні множини А i В такі, що n(A)=m і n(B)=k, причому АÇB=Ø. Якщо виконуються ці умови, то кількість елементів множини АÈВ визначається однозначно, тобто n(АÈВ)=m+k. Отже має місце таке твердження:

Правило суми: якщо множина А містить m елементів, а множина В - k елементів то множина AÈB містить m+k елементів.

Досить часто правило суми формулюють так:

Правило суми: якщо деякий елемент x з множини А можна вибрати m способами, а елемент y з множини В - k способами, причому жоден із способів вибору елемента x не співпадає зі способом вибору елемента y, то елемент x або елемент y можна вибрати m + k способами.

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

Задача 1: на столі є 4 ручки i 3 олівці. Скількома способами можна взяти зі столу один предмет?

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

У цій задачі маємо справу із двома скінченними множинами: А - множина ручок, де n(A)=4, i В - множина олівців, де n(B)=3. Оскільки нам потрібно вибрати один предмет, тобто зробити вибір x чи y (ручка або олівець), то згідно з правилом суми це можна зробити n(A)+n(B)=4+3=7 способами. Правило суми можна було застосувати тому, що множини не перетинаються i вибір ручки не залежить від вибору олівця i навпаки.

Задача 2: із 28 студентів групи: 15 - займається в секції волейболу, 12 – в секції футболу, 7 - займається в обох секціях. Скільки студентів займається в інших секціях.

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

У цій задачі мова йде про такі множини: А - множина студентів групи, де n(A)=28, В - множина студентів, які займаються волейболом, де n(B)=15, С - множина студентів, які займаються футболом, де n(C)=12, D - множина студентів, які займаються футболом i волейболом, де n(D=ВÇС)=7, K - множина студентів, які займаються в інших секціях, де n(K) потрібно знайти. На кругах Ейлера ці множини зобразяться так (див. малюнок № 21):