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

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 пасажири, ще в один - три і ще в один - решта двоє. Скільки є різних способів такого їх розташування?

      é Не так просто вибрати спосіб міркування для цієї задачі. "Розкручувати" її будемо поступово, за кілька послідовних кроків:

1. вибираємо, в які саме вагони сядуть по 4 пасажири ( , а не , бо порядок вибору не має значення );
2. з решти двох вагонів вибираємо ще, наприклад, той куди сядуть троє ( способів 2= ). Тепер нам відомо, в який вагон скільки пасажирів сяде. Починаємо їх розміщувати:
3. вибираємо 4 пасажири для одного з вагонів, де їх буде саме стільки: способів .

4), 5), 6) аналогічно: способів  , .

За основним принципом комбінаторики відповідь: .        

      Зауваження.    В цій    задачі не можна було б міркувати так: 1) виберемо, куди сяде перший пасажир - 4 способи; 2) … . Основний принцип комбінаторики тут не спрацював би, бо кількість способів для наступних етапів була б різною в залежності від того, як виконано попередні. 

3.Задачі на класичне означення ймовірності.

      Якщо  в умові задачі є слово "ймовірність", це вже не комбінаторна задача; але  швидше за все комбінаторика знадобиться. Перше, що потрібно зробити - з’ясувати  для себе, в чому полягає так  званий стохастичний експеримент задачі. Як правило, він описаний на початку  умови і результат його неможливо  взнати заздалегідь. Після цього  потрібно визначити, якими  можуть бути  результати експерименту і як їх можна  задати (наприклад, у вигляді розміщень  або комбінацій символів, щоб зручно було застосовувати комбінаторику), причому вони всі повинні бути однаково можливими. Тепер треба  визначити загальну можливу кількість  N результатів, або наслідків, а також скільки з них (K) є спиятливими для даної події А. Тут і буде корисною комбінаторика. Залишається поділити друге число на перше: .

      Приклад.  В групі 10 білявих та 15 чорнявих студентів. Навгад за списком вибирають двох. Яка ймовірність того, що з вибраних студентів один білявий та один чорнявий?

      Експеримент - відбір двох студентів з 25, кількість  рівноможливих результатів . Сприятливих буде , тому що потрібно вибрати для цього одного білявого й одного чорнявого.

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

      Стохастичний  експеримент задачі доводиться будувати самим, наприклад, як з’ясування днів народження першого, другого, …, k -го студента за списком. Способів маємо (29 лютого не враховується для спрощення). Кількість способів, коли якісь дні народження збігаються, безпосередньо порахувати важко; наприклад, правило добутку тут застосувати неможливо (переконайтесь у цьому). Застосуємо прийом "доповнення": решта варіантів - це ті, в яких всі дні народження різні, і їх . Тому відповідь .

Цікаво, що вже  при  k=23    , в що важко повірити недосвідченій людині. Спробуйте перевірити, що у випадковій аудиторії більше ніж з 23 осіб ймовірність співпадання днів народження досить велика, більша за 50%. 
 
 

4.Задачі на операції з множинами.

      З кожним стохастичним експериментом  пов’язують простір елементарних подій W - сукупність можливих наслідків експерименту. Всі випадкові події, пов’язані з даним стохастичним експериментом - підмножини в W ( тобто деякі набори можливих результатів). Тому теорія ймовірностей і теорія множин мають багато спільного: втім, вони говорять одне і те ж різними словами, що видно з такої таблиці:

      Приклад 8.  Нехай  А, В і С - довільні події. Що означають наступні події:

    ?

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

      Приклад 9.   Гральний кубик підкидають двічі. Описати простір елементарних подій. Описати події: А - сума очок, які з’явились, дорівнює 8; В - принаймі один раз з’явилось 6 очок. Що собою являє подія А Ç В?

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

W={ (1;1); (1;2); (1;3); …; (6;5); (6;6) }. Всього, очевидно, 36 різних елементів. Подію А задаємо перерахуванням елементів, які її складають:

А={сума очок дорівнює 8}={ (2,6); (3,5); (4,4); (5,3); (6,2) }.

Аналогічно В={ (6,1); (6,2); (6,3); (6,4); (6,5); (6,6); (1,6); (2,6); (3,6); (4,6); (5,6) }.

Подія АВ складається  з двох елементів, які входять  і в А, і в В: АВ={(2,6); (6,2)}.

      Це можна було б з’ясувати і безпосередньо з умови задачі: якщо здійснилась і подія А, і подія В, то на одному кубику повинно бути 6 очок, а на іншому, відповідно, 8-6=2. 
 

5.Задачі на застосування аксіом теорії ймовірностей

      Коли  виникла необхідність втиснути в  рамки логічної і стрункої схеми  теорію ймовірностей (до того вона базувалась більше на інтуітивних міркуваннях), А.Н. Колмогоровим було введено систему з 6 аксіом. Їх повинні були задовольняти такі об’єкти: Ω (простір елементарних наслідків), Р (ймовірність). Оскільки виявилось, що не можна усяку підмножину з Ω вважати випадковою подією, було введено окремо набір випадкових подій F. Тобто, "Ає F" еквівалентно "А-випадкова подія".

      Пояснити суть аксіом можна так. Перші три аксіоми означають, що набір F повинен задовольняти елементарні вимоги:1) все Ω є випадковою подією; 2) якщо якась підмножина з Ω входить в F, тобто А- випадкова подія, то "А не здійснилась" теж випадкова подія, тобто ; 3) якщо А₁, А₂, … - випадкові події, то є випадковою подія " здійснилась хоча б одна з подій  А₁, А₂, …".

      Друга група з трьох аксіом відноситься до поняття ймовірності: вони повністю узгоджуються з класичним та частотним означеннями ймовірності. Якщо вважати, що ймовірність події А –це число, що дорівнює її середній частоті за багато повторень експерименту, то аксіоми говорять: 1) це число невід’ємне і визначене для кожної випадкової події А (тобто Ає F); 2) середня частота Ω (достовірної події) дорівнює 1; 3) якщо події           А₁, А₂, … є несумісними, то середня частота їх об’єднання дорівнює сумі середніх частот. Дійсно, оскільки несумісні події можуть відбуватися тільки по одній, то відповідні кількості треба просумувати.

      Шість аксіом теорії ймовірностей становлять її міцну базу. Їх застосовують при розв’язанні багатьох задач.

      Приклад. Довести, що якщо А і В – випадкові події, то і - випадкова подія і Р( )=Р(А)+Р(В)-Р( ).

      Переформулюємо перше наше завдання так: якщо Ає F і ВєF, то є F. В аксіомах цього прямо не записано, але це не важко довести. Справді, , тобто . Оскільки Ає F і ВєF, то і (аксіома 2), тоді (аксіома 3), і звідси (знову аксіома 2), що й потрібно було довести.

      Далі, подію  можна подати як об’єднання трьох несумісних подій: “ А відбувається, В ні “, “ В відбувається, А ні “, “відбуваються і А, і В “, тобто

, і аналогічно

, .

Застосовуємо  аксіому 6:

,

,

.

З цих рівностей  неважко одержати потрібну формулу.

      Приклад. Нехай А і В – випадкові події, Р₀ – ймовірність того, що не відбудеться жодна з них, Р₁ – що відбудеться рівно одна, Р₂ –що відбудуться обидві. Виразити Р₀, Р₁, Р₂ через Р(А), Р(В), .

      Очевидно, Р₂= . Далі, доповненням до події є подія , ймовірність якої є шукана Р₀, тобто 1-Р( )=Р₀ і з попередньої задачі Р( )=Р(А)+Р(В)-Р( ); отже, Р₀=1-Р(А)-Р(В)+ .

      Знаючи  тепер Р₀ і Р₂ , можна легко знайти Р₁; справді, сума Р₀+Р₁+Р₂ повинна дорівнювати одиниці як сума ймовірностей трьох несумісних подій, об’єднання яких є W; отже, . 
 

6.Задачі на умовні ймовірності і незалежні події

      Умовною ймовірністю події А відносно події В називають число 

, при Р(В)¹0.

Щоб знайти його, отже, треба з’ясувати, що являє  собою подія  , знайти ймовірності її та події В і поділити.

      Умовну  ймовірність можна розуміти так: є інформація про те, що в результаті експерименту подія В відбулась. Яка за цієї умови ймовірність  події А? Це і є Р(А/В).

      В задачах часто застосовують очевидну формулу

 та її узагальнення .

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

Видно, що й В  тоді незалежна від А; коротко  кажуть, що А і В незалежні. Аналогічно визначається незалежність кількох  подій, а саме: події А₁,А₂, …, А_n називаються незалежними в сукупності, якщо ймовірність перетину будь-якого числа з них дорівнює добутку відповідних ймовірностей: . Зауважимо, що для такої незалежності недостатньо попарної незалежності подій.

      Приклад . Підкидають два гральні кубики. Знайти ймовірність того, що випаде хоч раз 6 очок, якщо відомо, що сума очок, що випали, не менша за 9.

      Конструкція "ймовірність…якщо відомо…", або  інакше: "ймовірність … за умови, що…" ясно вказує на умовну ймовірність. Очевидно, потрібно знайти Р(А/В), де А  – подія "випаде хоч раз 6 очок", В – "сума не менша за 9".

      В прикладі 9  ми вже з’ясували, який стохастичний експеримент, і знайшли  кількість (36) рівноможливих наслідків, що складають Ω. З цих результатів подія А є об’єднання рівно одинадцяти: (6,1); (6,2); …; (6,6); (1,6);…; (5,6), а подія В – восьми: (4,5); (5,4); (4,6); (5,5); (6,4); (5,6); (6,5); (6,6).

      Подія складається з п’яти випадків, що входять і в А, і в В: (4,6); (6,4); (5,6); (6,5); (6,6). Отже, .

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

      Нам потрібно знайти Р(А/В), де А є подія "друга куля біла", В – подія "перша куля біла".  

7.Випробування Бернуллі. Наближені формули для .