chap_0

Будемо говорити, що елемент ak має тип k. Наприклад, елемент a1 має тип 1. Уявимо, що елементи a1, яких є рiвно n1, перенумерованi числами вiд 1 до n1. Аналогiчно поступимо з рештою елементiв i одержимо множину з n1+n2+ +nk рiзних елементiв, бо вони тепер вiдрiзняються або типом, або номером. Розглянутi елементи дадуть (n1 + n2 + + nk)! перестановок, серед яких, зрозумiло, будуть i однаковi.

Якщо у фiксованнiй перестановцi ми почнемо переставляти мiсцями елементи a1 (а вони стоять на n1 мiсцях), то кожен раз будемо отримувати ту саму перестановку i число таких (однакових) перестановок буде рiвне n1!. Аналогiчнi мiркування стосуються решти елементiв. Згiдно головного принципу комбiнаторики число однакових перестановок становитиме n1!n2! : : : nk!. Якщо число всiх можливих перестановок подiлити на число однакових, то отримаємо вiдповiдь на поставлене питання у виглядi твердження.

Теорема 1.3. Число всiх рiзних перестановок з елементiв a1, a2,. . . , ak, якi повторюються вiдповiдно n1, n2, . . . ,nk разiв, визначається формулою

Приклад 1.6. Скiльки рiзних слiв, якi мають сенс або нi, можна утворити, переставляючи лiтери в словi "математика"?

Р о з в’ я з о к. Слова утворюємо, переставляючи 10 букв. Серед них буква "м\ повторюється два рази, буква "а\ три рази й буква "т\ 2 два рази. Отже, число рiзних слiв буде таким

10!

P10(2; 3; 2) = 2! 3! 2! = 151200:

Означення 1.3. Нехай дано множину H яка складається з n елементiв. Рiзнi пiдмножини, якi мiстять k елементiв множини H, називаться k-елементовими комбiнацiями даної множини H.

З а у в а ж е н н я. Для комбiнацiй не є iстотним порядок розташування елементiв. Так, наприклад, 3-елементовi пiдмножини f1; 2; 3g, f3; 2; 1g з множини f1; 2; 3; 4; 5g складають одну комбiнацiю.

Приклад 1.7. З множини H = fa; b; cg можемо утворити такi 2- елементовi комбiнацiї:

fa; bg; fa; cg; fb; cg:

Число всiх k-елементових комбiнацiй з n-елементової множини позначається символом Cnk: Для обчислення кiлькостi комбiнацiй можна користуватись наступними формулами

Приклад 1.8. З групи 10 спортсменiв потрiбно утворити команду

зчотирьох спортсменiв. Скiлькома способами це можна зробити?

Ро з в’ я з о к. Зрозумiло, що потрiбно знайти C104 :

Означення 1.4. Нехай дано множину H яка складається з n рiзних елементiв. Пiдмножини якi складаються з k елементiв множини H, причому цi елементи можуть повторюватися, називаються k-елементовими комбiнацiями з повтореннями з n- елементової множини.

Приклад 1.9. З елементiв a; b; c можемо утворити наступнi 2- елементовi комбiнацiї з повтореннями:

fa; ag; fa; bg; fa; cg; fb; bg; fb; cg; fc; cg:

Число всiх k-елементових комбiнацiй з повтореннями з n- еле-

ментової множини позначають символом k i обчислюють при

Cn

допомозi формули

1.2Контрольнi питання

1.Сформулюйте головний принцип комбiнаторики.

2.Дайте означення таким сполукам: перестановки, розмiщення та

комбiнацiї.

3.Дайте означення повторним та безповторним вибiркам.

4.Дайте означення розмiщенням та комбiнацiям з повтореннями.

5. Напишiть усi 2-елементовi комбiнацiї елементiв множини fa; b; cg.

6.Напишiть усi 2-елементовi комбiнацiї з повтореннями елементiв множини fa; b; cg.

7.Напишiть усi 2-елементовi розмiщення елементiв множини fa; b; c; dg.

8.Напишiть усi 2-елементовi розмiщення з повтореннями елемен-

тiв множини fa; b; c; dg.

9.Напишiть усi перестановки елементiв множини fa; b; cg.

10.Наведiть приклади розмiщень даного складу.

11.Чи може бути в комбiнацiї кiлька однакових елементiв?

12.Чи важливий порядок розташування елементiв в комбiнацiї?

13.Чи важливий порядок розташування елементiв в розмiщеннi?

14.Чи може бути в розмiщеннi кiлька однакових елементiв?

15.У чому полягає суттєва вiдмiннiсть мiж розмiщеннями та ком-

бiнацiями?

16.Що бiльше: Akn чи Akn+1+1?

17.Що бiльше: а) C2010 чи C205 ; б)C205 чи C216 ?

18.Доведiть рiвнiсть Cnk = Cnn k.

19.Доведiть рiвнiсть Cnk+1 = Cnk + Cnk 1.

20.Доведiть рiвнiсть Cnk = 2k.

21.Сформулюйте алгоритм побудови трикутника Паскаля.

22.Розкладiть вираз (1 + x)n у виглядi многочлена.

1.3Задачi роздiлу

1.1.Скiлькома способами можна розсадити 4 студентiв на 25 мiсцях? Вiдповiдь. 12650.

1.2.Скiлькома способами можна розмiстити k предметiв у n ящиках? Вiдповiдь. nk.

1.3.На вершину гори веде 7 дорiг. Скiлькома способами турист може пiднятись на гору i спуститися з неї? Дати вiдповiдь на те саме запитання, якщо пiдняття й спуск вiдбуваються рiзними шляхами. Вiдповiдь. 49; 42.

1.4.У розиграшу першостi країни з футболу бере участь 17 команд. Скiлькома способами можуть бути розподiленi золота, срiбна й бронзова медалi? Вiдповiдь. 17 16 15 = 4080.

1.5.На шести дисках автоматичної камери схову нанесено по 12 рiзних букв. Скiльки невдалих спроб може зробити особа, яка не знає секретного слова? Вiдповiдь. Число всiх варiантiв дорiвнює 126 =

248832. Значить невдалих спроб може бути 248831.

1.6.Група студентiв складається iз 10 хлопцiв та 15 дiвчат. У кiнцi навчання у групi було двi шлюбнi пари. Скiльки для цього iснувало варiантiв? Вiдповiдь. C152 C102 = 4725.

1.7.Скiльки тризначних чисел можна записати цифрами 0, 1, 2, 3, 4? Вiдповiдь. 100.

1.8.Скiлькома способами 7 осiб можуть стати в чергу до каси?

Вiдповiдь. 7!.

1.9.У групi студентiв вивчають 10 предметiв. У понедiлок 6 лекцiйних пар, причому всi вони рiзнi. Скiлькома способами можна скласти розклад на понедiлок? Вiдповiдь. A610.

1.10.Скiльки є п’ятизначних чисел, якi дiляться на 5?

Вiдповiдь. 9 10 10 10 2.

1.11. Скiльки дiагоналей має опуклий n-кутник? Вiдповiдь. n(n

3)=2.

1.12.Скiлькома способами можна розставити на шаховiй дошцi розмiрами n n двi рiзнокольоровi тури так, щоб вони не били одна одну? Вiдповiдь. n2(n 1)2.

1.13.Пасажир залишив речi в автоматичнiй камерi схову, а коли прийшов забирати речi, то виявилося, що вiн забув номер. Пасажир лише пам’ятає, що в номерi були числа 23 i 37. Щоб вiдкрити камеру, треба правильно набрати п’ятизначний номер. Яку найбiльшу кiлькiсть номерiв треба перебрати, щоб вiдкрити камеру?

Вiдповiдь. 60.

1.14. Скiлькома способами можна з 7 осiб вибрати комiсiю (голова, заступник та секретар), що складається з 3 осiб? Вiдповiдь.

7 6 5.

1.15. Скiлькома способами читач може вибрати 3 книжки з 6?

Вiдповiдь. C63 = 20.

1.16.Скiльки пiдмножин має множина, що мiстить n елементiв? (Вважати, що порожня множина є пiдмножиною кожної множини). Вiдповiдь. 2n.

1.17.У залi n лампочок. Скiльки всього є рiзних способiв її освiтлення, при яких горить рiвно k лампочок? Скiльки всього може бути рiзних способiв освiтлення зали? Вiдповiдь. Cnk; 2n.

1.18.Скiльки можна зробити перестановок iз n елементiв, у яких данi 2 елементи не стоять поруч? Вiдповiдь. (n 2)(n 1)!.

1.19.Скiлькома способами можна розмiстити на шаховiй дошцi 8 тур так, щоб вони не могли бити одна одну? Вiдповiдь. (8!)2 = 403202.

1.20.Скiльки слiв з п’яти букв можна утворити з букв а, b, c, якщо вiдомо, що буква а зустрiчається в словi не бiльше двох раз, b – не бiльше одного разу, с – не бiльше трьох раз?

Вiдповiдь. 5!=3! + 5!=(2! 3!) + 5!=(2! 2!) = 60.

1.21. Скiлькома способами можна подiлити 3n рiзних предметiв мiж трьома особами так, щоб кожна особа одержала n предметiв?

Вiдповiдь. C3nnC2nnCnn.

1.22. Скiлькома способами можна вибрати 6 однакових або рiзних лазерних принтерiв, якщо на базi їх є 11 рiзних типiв?

Вiдповiдь. C1610. Скористатись формулою для числа комбiнацiй з повторення-

1.23. Скiльки iснує рiзних трикутникiв, довжини сторiн яких можуть набувати таких значень: 4, 5, 6 та 7 см?

1.24. Скiльки можна побудувати прямокутних паралелепiпедiв, довжини ребер яких виражаються натуральними числами вiд 1

1.25. Мiжнародна комiсiя складається з 9 осiб. Матерiали комiсiї зберiгаються в сейфi. Скiльки замкiв повинен мати сейф, скiльки

ключiв до них треба виготовити i як їх розподiлити серед членiв комiсiї, щоб доступ до сейфа був можливий тодi i тiльки тодi, коли збереться не менше 6 членiв комiсiї? Розглянути задачу для випаду, коли комiсiя складається з n осiб, а сейф можна вiдкрити лише при наявностi не менше m членiв комiсiї.

Вiдповiдь. Якi б (m 1) членiв комiсiї не зiбрались, повинен знайтись замок, який вони не можуть вiдiмкнути, але ключ до цього замка є у кожного з решти (n m + 1) членiв комiсiї. Тому мiнiмальне число замкiв дорiвнює Cnm 1, а число ключiв (n m + 1)Cnm 1.

1.26. У класi 35 учнiв. З них 20 вiдвiдують математичний гурток, 11 – фiзичний, а 10 учнiв не вiдвiдують жодного гуртка. Скiльки учнiв вiдвiдують математичний та фiзичний гуртки? Скiльки учнiв вiдвiдують лише математичний гурток?

Вiдповiдь. 6; 14. Скористатись формулою для числа елементiв суми двох мно-

жин: N(A+B) = N(A)+N(B) N(AB), де N( ) – число елементiв множини

.

1.27. Iз 100 студентiв англiйську мову знають 28 студентiв, нiмецьку – 30, французьку – 42, англiйську i нiмецьку – 8, англiйську i французьку – 10, нiмецьку й французьку – 5, всi 3 мови знають 3 студенти. Скiльки студентiв не знають жодної з трьох мов?

Вiдповiдь. 20. Скористатись формулою для числа елементiв суми трьох множин: N(A + B + C) = N(A) + N(B) + N(C) N(AB) N(AC) N(BC) +

N(ABC), де N( ) – число елементiв множини .

1.28. У жорстокому бою не менше 70% бiйцiв утратили одне око, не менше 75% – одне вухо, не менше 80% – одну руку i не менше 85% – одну ногу. Яка мiнiмальна кiлькiсть бiйцiв, якi втратили одночасно око, вухо, руку й ногу? (Льюис Кэррол. История с узелками. М., "Мир 1973).

Вiдповiдь. Найменша кiлькiсть бiйцiв, що брали участь у бою дорiвнює 20. З них 14 бiйцiв втратили одне око, 15 – одне вухо, 16 – одну руку i 17 бiйцiв утратили одну ногу. Мiнiмальне число бiйцiв, що втратили одночасно око, вухо, руку й ногу дорiвнює 2.

20 РОЗДIЛ 2. СТОХАСТИЧНИЙ ЕКСПЕРИМЕНТ

повторити яке завгодно число разiв за даних незмiнних умов. Приклад 2.1 (пiдкидання монети). Пiдкидаючи монету, матимемо два можливi реультати: герб або цифра. Перед її пiдкиданням ми не можемо точно передбачити який буде результат, оскiльки дуже багато факторiв (деякi iз них нам навiть не вiдомi) впливають на результат кожного пiдкидання. Серед цих факторiв можна назвати такi: початкова швидкiсть монети, кут, пiд яким викинуто монету, ступiнь гладкостi поверхнi столу на який падає монета, та багато iнших. Взагалi кажучи, iснують сотнi параметрiв вiд яких залежить результат пiдкидання монети. I оскiльки ми не в змозi регулювати всi цi параметри, то i не можемо передбачити результат експерименту.

Приклад 2.2 (дворазове пiдкидання монети). Експеримент полягає в тому, що монету пiдкидаємо два рази. Якщо позначимо випадання герба лiтерою Г, а цифри лiтерою Ц, то можливi результати нашого експерименту можна зобразити так ГГ , ГЦ , ЦГ , ЦЦ, де, наприклад, ГЦ означає, що спочатку випав герб, а потiм цифра. Приклад 2.3 (пiдкидання кубика). Експеримент полягає у пiдкиданнi шестигранного кубика з пронумерованими граннями. Можливi результати цього експерименту будуть такими: 1, 2, 3, 4, 5, 6. Ситуацiя тут є така сама як i в першому прикладi, тобто ми не можемо напевно предбачити якою гранню випаде кубик.

Приклад 2.4 (дворазове пiдкидання кубика). Експеримент полягає в тому, що ми пiдкидаємо кубик два рази. Можливi результати експерименту можна зобразити парами цифр (i; j), де i; j = 1; 2; : : : ; 6.

У всiх попереднiх прикладах число можливих результатiв експерименту було скiнченним. Неважко навести приклади, де таких можливих результатiв буде нескiнченна кiлькiсть.

Приклад 2.5. Будемо пiдкидати монету до тих пiр, поки не випаде перший раз герб, пiсля чого експеримент припиняємо. Результати такого експерименту можна подати у виглядi послiдовностей (ЦЦ. . . ЦГ). Очевидно, число таких послiдовностей буде нескiнченним.

Приклад 2.6 (задача про зустрiч). Двi особи A та B домовилися про зустрiч у iнтервалi часу [a; b]. Якщо позначити через x

момент приходу A, а через y момент приходу B, то кожна пара чисел (x; y), де a x b, a y b, може бути результатом такого експерименту. Очевидно, що число таких пар чисел буде нескiнченним.

Тепер перейдемо до пояснення сутностi елементарної подiї. Подiї А, В, С i т.д. називаються взаємно несумiсними в даному експериментi, якщо настання (поява) однiєї подiї виключає можливiсть настання будь-якої iншої.

Означення 2.1. Взаємно несумiснi результати стохастичного експерименту називаються елементарними подiями.

Означення 2.2. Множина всiх елементарних подiй стохастичного експерименту називається простором елементарних подiй i позначається лiтерою . Iншими словами, якщо розглядається певний стохастичний експеримент S, то є множиною всiх можливих результатiв цього експерименту.

Приклад 2.7. В прикладi 2.1 простiр елементарних подiй буде таким: = fГ; Цg, у прикладi 2.2 – = fГГ; ГЦ; ЦГ; ЦЦg,

fГ; ЦГ; ЦЦГ; ЦЦЦГ; ЦЦЦЦГ; : : :g, а в прикладi 2.6 – = f(x; y) : a x b; a y bg.

Кожну пiдмножину A з простору будемо називати подiєю. Якщо в стохастичному експериментi маємо деякий результат ! i ! 2 A, то будемо говорити, що вiдбулася подiя A i що елементарна подiя ! сприяє подiї A.

Порожню множину позначимо буквою ;. Оскiльки завжди

i ; , то множини i ; є подiями. Перша з них називається достовiрною або певною подiєю, натомiсть друга – подiя неможлива.

Приклад 2.8 (дворазове пiдкидання моненти). В цiй ситуацiї (приклад 2.2) = fГГ; ГЦ; ЦГ; ЦЦg i, якщо подiя A полягає в тому, що два рази випаде герб, то A = fГГg, а якщо подiя B полягає в тому, що хоча б один раз випаде герб, то B = fГГ; ГЦ; ЦГg. Елементарна подiя fГГg сприяє подiям A та B, а елементарна подiя fГЦg сприяє подiї B, але не сприяє подiї A.

Приклад 2.9 (пiдкидання кубика). Маємо = f1; 2; 3; 4; 5; 6g i, нехай подiя A полягає в тому, що випало парне число очок, тобто A = f2; 4; 6g, i тодi елементарна подiя f4g сприяє подiї A, а елементрна подiя f3g нi.

ма очок при двох пiдкиданнях рiвна 5, то A = f(i; j) : i + j = 5g, або, що те саме A = f(1; 4); (2; 3); (3; 2); (4; 1)g.

2.2Дiї над подiями

Оскiльки випадковi подiї трактуються як пiдмножини множини, то дiї над подiями можна означити так само як i дiї над множинами. Це означає, що, наприклад, суму двох подiй A та B можна означити як третю подiю C, що складається лише з тих елементарних подiй, якi належать або до A, або до B. Але, в теорiї ймовiрностей використовують притаманну їй термiнологiю. Це означає, що ми будемо говорити про настання вiдповiдної подiї. Так сума подiй у терiї ймовiрностей визначається так:

Означення 2.3. Сумою або об’єднанням двох випадкових подiй

A та B називається така подiя, яка настає тодi та лише тодi, коли настає хоча б одна з подiй A чи B (або обидвi разом).

Сума подiй A та B позначається A + B або A [ B. З цього означення випливає, що подiя A + B складається лише з тих елементарних подiй, якi належать або до A, або до B, або до обох подiй разом.

Приклад 2.11. Розглянемо при яких умовах можлива рiвнiсть A+ B = A. Оскiльки сума включає кожний з доданкiв, то B A. На мовi подiй це спiввiдношення означає, що подiя B сприяє подiї A.

Приклад 2.12 (дворазове пiдкидання кубика). Розглянемо подiї:

A = f(i; j) : i + j 7g;

B = f(i; j) : 4 i + j < 10g;

C = f(i; j) : 8 i + j 9g: