Задачі з комбінаторики та теорії ймовірності

Размещено на http://www.allbest.ru/

Задачі з комбінаторики

В подальшому вам часто знадобиться вміння підраховувати кількість способів, варіантів (ще можна сказати - різних наслідків, результатів) настання певної події або виконання деякої дії. Наприклад: скільки є різних початкових положень при грі в преферанс? Скільки є різних способів освітлення кімнати, якщо в ній розміщені 5 світильників, кожний з яких можна ввімкнути та вимкнути незалежно від інших?

Найголовніше правило, яке "працює" при розв'язанні подібних задач - це так зване правило добутку; ще його називають основним принципом комбінаторики. Сформулюємо та пояснимо його спочатку в більш простому вигляді, одночасно з правилом суми; потім - у більш загальному.

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

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

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

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

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

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

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

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

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

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

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

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

.

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

.

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

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

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

Спосіб 2. Для першого світлофора 3 варіанти сигналу, для другого, третього і т.д. - теж. Оскільки нам треба вибрати і сигнал першого, і другого,…, і п'ятого, то діє правило добутку: 33333=243.

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

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

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

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

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

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

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

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

вибираємо, в які саме вагони сядуть по 4 пасажири ( , а не , бо порядок вибору не має значення );

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

вибираємо 4 пасажири для одного з вагонів, де їх буде саме стільки: способів .

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

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

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

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

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

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

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

Відповідь: .

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

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

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

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

комбінаторика ймовірність випробування бернуллі

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

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

?

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

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

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

={ (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.

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

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

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

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

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

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

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

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

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

, .

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

,

,

.

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

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

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

Знаючи тепер Р0 і Р2 , можна легко знайти Р1; справді, сума Р0+Р1+Р2 повинна дорівнювати одиниці як сума ймовірностей трьох несумісних подій, об'єднання яких є ; отже, .

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

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

, при Р(В)0.

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

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

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

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

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

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

Приклад 12 . Підкидають два гральні кубики. Знайти ймовірність того, що випаде хоч раз 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. З урни, що містить білих та чорних куль, послідовно виймають дві кулі (без повернення). Знайти ймовірність того, що друга куля біла, якщо відомо, що перша куля біла.

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

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

На практиці часто зустрічаються ситуації, які можна розглядати як проведення певної кількості n окремих експериментів (випробувань), які є незалежними і в результаті кожного з яких певна подія (“успіх”) може статись з однією і тією ж ймовірністю p. Такі випробування прийнято називати випробуваннями Бернуллі.

Приклад: Сподіваючись на приз від компанії “Кока-кола”, ви протягом року кожного тижня купуєте по пляшці цього напою. В середньому кожна двохсота пляшка має кришечку зі знаком призу.

В даному випадку n = ?, p = ?

В лекціях виведено формулу для ймовірності того, що в даній серії з n випробувань Бернуллі відбудеться рівно k успіхів:

Якщо n та k великі, можна використовувати наближені формули:

локальну Муавра-Лапласа

, - щільність стандартного нормального розподілу, а - ймовірність “неуспіху”;

інтегральну Муавра-Лапласа

,

де , для формула аналогічна, а значення функції Лапласа беруться з таблиць;

формулу Пуассона (для малих p)

, де .

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

Размещено на Allbest.ru