Елементи комбінаторики

1.Поняття множини. Операції над множинами 

     Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як сукупність деяких предметів, об'єднаних за довільною характеристичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій

     Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинського алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації можна позначити буквою М (чи будь-якою великою буквою латинського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}

     Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А, де А - множина чисел першого десятка, а число 12 A.

     Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним числом Наприклад, множина М цифр десяткової нумерації скінченна і містить десять елементів. У нескінченній множині - нескінченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.

     Множина, в якій немає жодного елемента, називається порожньою і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина

     Якщо множина В складається з деяких елементів даної множини А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами А і В позначається так В А (читається "В міститься в А" або "В — підмножина А"). Якщо В може й дорівнювати А, то вживається символ В А. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.

Порожня множина  є підмножиною будь-якої множини, тобто А.

Саму множину  А можна розглядати як підмножину А, тобто А А.

     Множину задають двома основними способами:

1) переліченням  всіх її елементів;

2) описанням  характеристичної властивості її  елементів. Наприклад: а) В = {o,,Ў} - множина, задана переліченням  елементів; б) X - множина коренів  квадратного рівняння х2 = 25. Множина  X задана характеристичною властивістю  елементів - бути коренем рівняння  х2 = 25". Цю саму множину можна  задати і переліченням її елементів: X = {-5; 5}.

     Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|-5. Отже, X = Y.

    Над множинами виконуються певні операції (дії). Зазначимо три з них.

    Переріз множин. Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елементів, які належать коленій з даних множин А і В.

   

 Приклад. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників числа 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.

Схематично переріз  множин А і В можна зобразити  за допомогою фігур. Символічно позначається так: С = А В і читається: "С є перерізом А і В".

    

Приклад. Нехай М - множина прямокутників, N - множина ромбів, тоді Р = М N - множина квадратів.

Об'єднання множин. Об'єднанням (або сумою) двох множин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.

Позначається  це так: С = А В і читається: "С  є об'єднанням А і В".

Якщо множини  А і В мають спільні елементи, тобто А В 0, то кожний з цих  спільних елементів береться в множину  С тільки один раз.

   

 Приклад. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}. 

 Приклад. Q - множина раціональних чисел, І - множина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q І.

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

Віднімання множин. Доповнення множини. Різницею двох множин А і В називається така множина  С, яка складається з усіх елементів  множини А, що не належать множині  В.

Позначається  це так: С = А \ В і читається: "С  є різницею А і В".

   

 Приклад. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В А, тоді С = А \ В= {8, 12};

б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};

в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};

г) А= {5, 6}, В= {5,6, 12}, тобто В А, тоді С = А\ В = .

У випадку, коли А В, то різниця С = А \ В називається  доповненням множини В відносно множини А і позначається САВ.

 

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

Якщо  вибрати елемент  A можна m  способами, а   В - n способами, то вибір "А або В" можна здійснити m+n способами, а "А і В" - mn  способами.

Приклад. Якщо ви бачите в аудиторії 3 дівчини  та 5 юнаків, то вибрати дівчину (одну) можна, звичайно, трьома способами, а  юнака - п’ятьма. Вибір "дівчину або  юнака", тобто довільну особу з  присутніх, можна здійснити 3+5=8 способами, бо цих присутніх саме стільки. Вибрати  ж дівчину та юнака можливо  саме 3´5=15 різними способами. Справді. для кожної з трьох різних дівчат може бути вибраний ще будь-який з п’яти юнаків. Отже, способів 5+5+5= 5´3=15.

      Основний  принцип комбінаторики. (загальне формулювання). Нехай певну дію (наприклад, вибір) можна виконати за k послідовних кроків, і два способи виконання є різними, якщо хоч на одному кроці вони відрізняються. Якщо кількості способів, якими можна виконати перший, другий, …, k-й етапи відповідно дорівнюють n₁, n₂, …, n_k і не залежать від того, як виконувались попередні етапи, то кількість різних способів виконання всієї дії дорівнює добутку n₁´ n₂´ … ´ n_k.

      Проілюструємо дію основного принципу комбінаторики (далі - ОПК) на кількох важливих прикладах.

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

      éСпосіб 1. Ці результати можна просто виписати: ГГГ, ГГР (цей результат означає, що спочатку монета двічі впала гербом, а потім  - решкою), ГРГ, ГРР, РГГ, РГР, РРГ, РРР. Всього  8 різних.

      Спосіб 2.  Одержати певний результат трикратного  кидання монети, можна, послідовно розглядаючи  можливості при першому, другому  та третьому киданні. На мові вище розглянутих  послідовностей з трьох літер  це означає: записати таку послідовність ( і повністю визначити цим один окремий результат) можна, вибравши спочатку першу літеру, потім другу, потім третю. Для кожного кроку маємо 2 можливості, тобто 2 способи - Г або Р. Всього за ОПК способів  2´2´2=8.                        û  

      Зауваження 1. Хоч у задачі цього явно не сказано, ми враховували послідовність випадання гербів та решок. Інакше результатів було б всього чотири: три герби, два герби і одна решка, один герб і дві решки, три решки. Таких способів підрахунку ми будемо уникати з-за того, що тут різні результати не є рівноможливими: порівнявши з попередніми міркуваннями, бачимо, що "два герби і одна решка" втричі можливіше за "три герби".

      Зауваження 2.  Міркуючи аналогічно до способу 2, приходимо до формули для кількості так званих розміщень з повтореннями , тобто впорядкованих послідовностей з k елементів, кожний з яких може бути будь-яким з даної множини, в якій n різних елементів:

            

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

            

Справді, для першого елемента послідовності  маємо n способів вибору, для другого n-1 (якщо вже вибраний перший, то другий не може з ним співпадати) і т.д. У випадку, коли розміщуємо в деякому порядку k різних елементів, маємо розміщення без повторень з k елементів по k, або, простіше перестановку з k елементів.  Кількість таких перестановок рахується аналогічно з застосуванням  ОПК.

                         

      Одержані  нами формули дуже корисні, тому що в багатьох задачах вибір способу  дії   фактично зводиться до вибору розміщення, або перестановки, або  так званої комбінації з n елементів по k. Це будь-яка підмножина з k елементів даної n - елементної множини. Формула для кількості таких комбінацій:

             .

Вона  виведена в курсі лекцій, як і  формула для кількості перестановок з повтореннями (коли переставляють  n елементів, з яких деякі однакові, а саме n₁ однакових одного типу, n₂ - другого, …, n_л - k - го, де n₁+ n₂+…+ n_л=n)

             .

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

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

      é Спосіб 1. Перенумеруємо світлофори і кожний варіант задаватимемо послідовністю з п’яти символів, кожний з яких Ч, Ж, З. Маємо розміщення (з повтореннями) з трьох елементів по п’ять. Їх кількість

      Спосіб 2.  Для першого світлофора  3  варіанти сигналу, для другого, третього і т.д. - теж. Оскільки нам  треба вибрати і сигнал першого, і другого,…, і п’ятого, то діє  правило добутку: 3´3´3´3´3=243.           Приклад 4.  Три рази кидають гральний кубик. Скільки може бути різних наслідків при цьому? В скількох з них є хоч одна "шістка"? Рівно одна шістка, а два інші результати однакові?

      éЗа правилом добутку або за формулою   кількість всіх способів 6´6´6=216. Щоб знайти відповідь на наступне питання, застосуємо так званий прийом "знаходження доповнення". Запитаємо себе, що собою уявляє "решта" варіантів? Це варіанти, де нема жодної шісткі, тобто могли випадати тільки грані 1, 2, 3, 4, 5. Але ж їх тоді легко порахувати: за тим же правилом добутку їх кількість 5´5´5=125. Тоді тих наслідків, де є хоч одна "шістка",              216-125=91.

      Щоб відповісти на останнє запитання, уявимо собі, що ми вибираємо, тобто визначаємо потрібний нам варіант, за такі кроки: 1) вибираємо, яка ще грань буде випадати, крім шістки;

2) розставляємо  у певному порядку три відомі  грані, з яких дві однакові. На першому кроці способів, очевидно, 5, на другому 3 ( це можна встановити  багатьма способами: наприклад,  взагалі за формулою  P₃(2,1)).

Оскільки  цим варіант визначається однозначно, то маємо відповідь за ОПК 5´3=15.          û

      Зауваження.  Як правило, як тільки в умові задачі зустрічається зворот "хоча б  одна", треба відразу застосовувати  прийом "знаходження доповнення".

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