3.2: Комбінації

Освоївши перестановки, розглянемо тепер комбінації. \(U\)Дозволяти бути набір з\(n\) елементами; ми хочемо підрахувати кількість різних підмножин множини\(U\), які мають саме\(j\) елементи. Порожня множина і множина\(U\) вважаються підмножинами\(U\). Порожній набір зазвичай позначається символом\(\phi\).

Приклад\(\PageIndex{5}\):

Нехай\(U = \{a,b,c\}\). Підмножини\(U\) є\[\phi,\ \{a\},\ \{b\},\ \{c\},\ \{a,b\},\ \{a,c\},\ \{b,c\},\ \{a,b,c\}\ .\]

Біноміальні коефіцієнти

Кількість різних підмножин з\(j\) елементами, які можуть бути обрані з множини з\(n\) елементами позначається\({n \choose j}\), і вимовляється «\(n\)вибрати»\(j\). Число\(n \choose j\) називається біноміальним коефіцієнтом. Ця термінологія походить від програми до алгебри, яка буде розглянута далі в цьому розділі.

У наведеному вище прикладі існує одна підмножина без елементів, три підмножини з рівно 1 елементом, три підмножини з рівно 2 елементами і одна підмножина з рівно 3 елементами. Таким чином\({3 \choose 0} = 1\),\({3 \choose 1} = 3\),,\({3 \choose 2} = 3\), і\({3 \choose 3} = 1\). Зверніть увагу, що у всіх є\(2^3 = 8\) підмножини. (Ми вже бачили, що набір з\(n\) елементами має\(2^n\) підмножини; див. Вправа 3.1.8) З цього випливає, що

\[{3 \choose 0} + {3 \choose 1} + {3 \choose 2} + {3 \choose 3} = 2^3 = 8\ ,\]\[{n \choose 0} = {n \choose n} = 1\ .\]

Припустимо, що\(n > 0\). Тоді, оскільки існує лише один спосіб вибрати набір без елементів і тільки один спосіб вибрати набір з\(n\) елементами, інші значення\(n \choose j\) визначаються наступним:

Теорема\(\PageIndex{1}\)

Для цілих чисел\(n\) і\(j\), з\(0 < j < n\), біноміальні коефіцієнти задовольняють:

\[{n \choose j} = {n-1 \choose j} + {n-1 \choose j - 1}\ . \label{eq 3.3}\]

Доказ

Ми хочемо вибрати підмножину\(j\) елементів. Вибираємо\(u\) елемент\(U\). Припустімо спочатку, що ми не хочемо\(u\) в підмножині. Потім ми повинні вибрати\(j\) елементи з набору\(n - 1\) елементів; це можна зробити\({n-1 \choose j}\) способами. З іншого боку, припустимо, що ми хочемо\(u\) в підмножині. Потім ми повинні вибрати інші\(j - 1\) елементи з інших\(n - 1\) елементів\(U\); це можна зробити\({n-1 \choose j - 1}\) способами. Оскільки\(u\) є або в нашій підмножині, чи ні, кількість способів, які ми можемо вибрати підмножину\(j\) елементів є сумою кількості підмножин\(j\) елементів, які мають\(u\) як член, і число, які не роблять - це те, що рівняння 3.1.1 стверджує.

Біноміальний коефіцієнт\(n \choose j\) визначається рівним 0, if\(j < 0\) або if\(j > n\). При такому визначенні обмеження в\(j\) теоремі\(\PageIndex{1}\) є непотрібними.

Трикутник Паскаля

Відношення 3.1 разом зі знаннями, які\[{n \choose 0} = {n \choose n }= 1\ ,\] визначають повністю числа\(n \choose j\). Ми можемо використовувати ці відносини для визначення відомого, який виставляє всі ці числа в матричному вигляді (див. Рис.

У\(n\) рядку цього трикутника є записи\(n \choose 0\),\(n \choose 1\),...,\(n \choose n\). Ми знаємо, що перше і останнє з цих чисел - 1. Решта чисел визначаються співвідношенням повторення Equation 3.1; тобто запис\({n \choose j}\) для\(0 < j < n\) у\(n\) -му рядку трикутника Паскаля є запис безпосередньо вище, а той, що безпосередньо ліворуч від нього в\((n - 1)\) першому рядку. Наприклад,\({5 \choose 2} = 6 + 4 = 10\).

Цей алгоритм побудови трикутника Паскаля може бути використаний для написання комп'ютерної програми для обчислення біноміальних коефіцієнтів. Вас просять зробити це у вправі 4.

Хоча трикутник Паскаля забезпечує спосіб рекурсивно побудови біноміальних коефіцієнтів, також можна дати формулу для\(n \choose j\).

Теорема\(\PageIndex{1}\)

Біноміальні коефіцієнти задаються за формулою\[{n \choose j }= \frac{(n)_j}{j!}\ . \label{eq 3.4}\]

Доказ

Кожну\(j\) підмножину розміру набору розміру\(n\) можна впорядкувати\(j!\) способами. Кожен з цих порядків являє собою\(j\) -перестановку набору розміру\(n\). Кількість\(j\) -перестановок є\((n)_j\), тому кількість підмножин розміру\(j\) є\[\frac{(n)_j}{j!}\ .\] Це завершує доказ.

Вищевказану формулу можна переписати у вигляді\[{n \choose j} = \frac{n!}{j!(n-j)!}\ .\] Це відразу показує, що\[{n \choose j} = {n \choose {n-j}}\ .\]

При використанні Рівняння 3.2 при обчисленні\({n \choose j}\), якщо чергувати множення і ділення, то всі проміжні значення в обчисленні є цілими числами. Крім того, жодне з цих проміжних значень не перевищує кінцевого значення. (Див. Вправу 40.)

Ще один момент, який слід зробити стосовно Equation [eq 3.4], полягає в тому, що якщо воно використовується для біноміальних коефіцієнтів, то більше не потрібно вимагати,\(n\) щоб бути додатним цілим числом. Змінна все ще\(j\) повинна бути невід'ємним цілим числом під цим визначенням. Ця ідея корисна при розширенні Біноміальної теореми до загальних показників. (Біноміальна теорема для невід'ємних цілих показників наведена нижче як теорема [thm 3.9].)

Руки для покеру

Приклад\(\PageIndex{6}\):

Гравці в покер іноді задаються питанням, чому ударів в покер рука є випадковим підмножиною 5 елементів з колоди 52 карт. Рука має чотири види, якщо вона має чотири карти з однаковим значенням - наприклад, чотири шістки або чотири королі. Це повний будинок, якщо він має три з одного значення і дві секунди - наприклад, три двійки та дві королеви. Давайте подивимося, яка рука є більш імовірною. Скільки рук мають чотири в своєму роді? Є 13 способів, які ми можемо вказати значення для чотирьох карт. Для кожного з них передбачено 48 можливостей для п'ятої карти. Таким чином, кількість чотирьох в своєму роді рук є\(13 \cdot 48 = 624\). Оскільки загальна кількість можливих рук є\({52 \choose 5} = 2598960\), ймовірність руки з чотирма видами є\(624/2598960 = .00024\).

Тепер розглянемо випадок аншлагу; скільки таких рук там? Є 13 варіантів для значення, яке відбувається три рази; для кожного з них є\({4 \choose 3} = 4\) вибір для конкретних трьох карт цього значення, які знаходяться в руці. Вибравши ці три карти, є 12 можливостей для значення, яке відбувається двічі; для кожної з них є\({4 \choose 2} = 6\) можливості для конкретної пари цього значення. Таким чином, кількість аншлагів є\(13 \cdot 4 \cdot 12 \cdot 6 = 3744\), а ймовірність отримання руки з аншлагом є\(3744/2598960 = .0014\). Таким чином, хоча обидва типи рук малоймовірні, ви в шість разів більше шансів отримати аншлаг, ніж чотири подібного роду.

Випробування Бернуллі

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

Визначення\(\PageIndex{1}\)

Бернуллі - це послідовність\(n\) випадкових експериментів, таких, що

1. Кожен експеримент має два можливі результати, які ми можемо назвати і

2. \(p\)Імовірність успіху на кожному експерименті однакова для кожного експерименту, і на цю ймовірність не впливає жодне знання попередніх результатів. \(q\)Імовірність виходу з ладу задається\(q = 1 - p\).

Приклад\(\PageIndex{7}\)

Нижче наведено процеси випробувань Бернуллі:

1. Монету кидають десять разів. Два можливих результату - орел і решка. Імовірність голів на якомусь одному киданні дорівнює 1/2.

2. Опитування громадської думки проводиться шляхом запитування 1000 людей, випадково обраних від населення, якщо вони виступають за поправку про рівні права - два результати - так і ні. \(p\)Імовірність відповіді «так» (тобто успіх) вказує на частку людей у всьому населенні, які виступають за цю поправку.

3. Азартний гравець робить послідовність 1-доларових ставок, роблячи ставку кожен раз на чорне в рулетці в Лас-Вегасі. Тут успіх виграє 1 долар, а невдача втрачає 1 долар. Так як в американській рулетці азартний гравець виграє, якщо м'яч зупиниться на одній з 18 з 38 позицій і програє інакше, ймовірність виграшу є\(p = 18/38 = .474\).

Щоб проаналізувати процес випробувань Бернуллі, ми обираємо як простір вибірки бінарне дерево і призначаємо розподіл ймовірностей для шляхів у цьому дереві. Припустимо, наприклад, що у нас три випробування Бернуллі. Можливі результати вказані на деревоподібній діаграмі, наведеній на малюнку 3.4. \(X\)Визначено випадкову величину, яка представляє результат процесу, тобто впорядковану трійку S і F. Імовірності, присвоєні гілкам дерева, представляють ймовірність для кожного окремого випробування. Нехай результат випробування позначається випадковою величиною\(X_i\), з функцією розподілу\(m_i\).\(i\) Оскільки ми припустили, що результати будь-якого одного випробування не впливають на результати іншого, ми призначаємо однакові ймовірності на кожному рівні дерева. \(\omega\)Результатом всього експерименту буде шлях через дерево. Наприклад,\(\omega_3\) представляє результати ДФС. Наша частотна інтерпретація ймовірності призведе до того, що ми очікуємо\(p\) частки успіхів на першому експерименті;\(q\) з них частка невдач на другому; і, з них,\(p\) частка успіхів на третьому експерименті. Це говорить про присвоєння ймовірності\(pqp\) результату\(\omega_3\). Більш загально, ми призначаємо функцію розподілу\(m(\omega)\) для шляхів,\(\omega\)\(m(\omega)\) визначаючи як добуток ймовірностей гілки вздовж шляху\(\omega\). Таким чином, ймовірність того, що три події S на першому випробуванні, F на другому випробуванні, і S на третьому випробуванні відбуваються, є продуктом ймовірностей для окремих подій. У наступному розділі ми побачимо, що це означає, що події, пов'язані з цим, полягають у тому сенсі, що знання однієї події не впливає на наше передбачення виникнення інших подій.

Біноміальні ймовірності

Нас буде особливо цікавити ймовірність того, що в випробуваннях\(n\) Бернуллі є саме\(j\) успіхи. Позначимо цю ймовірність шляхом\(b(n,p,j)\). Розрахуємо конкретне значення\(b(3,p,2)\) з нашого дерева міри. Ми бачимо, що є три шляхи, які мають рівно два успіхи і один провал\(\omega_2\), а саме\(\omega_3\), і\(\omega_5\). Кожен з цих шляхів має однакову ймовірність\(p^2q\). Таким чином\(b(3,p,2) = 3p^2q\). Враховуючи всі можливі успіхи, які ми маємо

\[\begin{aligned} b(3,p,0) &=& q^3\ ,\\ b(3,p,1) &=& 3pq^2\ ,\\ b(3,p,2) &=& 3p^2q\ ,\\ b(3,p,3) &=& p^3\ .\end{aligned}\]Таким же чином ми можемо провести деревоподібну міру для\(n\) експериментів і визначити\(b(n,p,j)\) для загального випадку випробувань\(n\) Бернуллі.

Теорема\(\PageIndex{2}\)

Враховуючи випробування\(n\) Бернуллі з\(p\) ймовірністю успіху на кожному експерименті, ймовірність саме\(j\) успіхів є\[b(n,p,j) = {n \choose j} p^j q^{n - j}\] де\(q = 1 - p\).

Доказ

Побудуємо деревоподібну міру, як описано вище. Ми хочемо знайти суму ймовірностей для всіх шляхів, які мають саме\(j\) успіхи та\(n - j\) невдачі. Кожному такому шляху присвоюється ймовірність\(p^j q^{n - j}\). Скільки таких стежок існує? Щоб вказати шлях, ми повинні вибрати з\(n\) можливих випробувань підмножину\(j\) успіху, а решта\(n-j\) результатів - невдачі. Ми можемо зробити це\(n \choose j\) способами. Таким чином, сума ймовірностей\[b(n,p,j) = {n \choose j} p^j q^{n - j}\ .\]

Приклад\(\PageIndex{8}\):

Справедлива монета підкидається шість разів. Яка ймовірність того, що рівно три голови з'являться вгору? Відповідь:\[b(6,.5,3) = {6 \choose 3} \left(\frac12\right)^3 \left(\frac12\right)^3 = 20 \cdot \frac1{64} = .3125\ .\]

Приклад\(\PageIndex{9}\):

Плашку прокочують чотири рази. Яка ймовірність того, що ми отримаємо рівно одну 6? Ми ставимося до цього як випробування Бернуллі з успіхом = «прокатка 6" і невдача = «прокатка деякого числа, крім 6». Тоді\(p = 1/6\), і ймовірність рівно одного успіху в чотирьох випробуваннях\[b(4,1/6,1) = {4 \choose 1 }\left(\frac16\right)^1 \left(\frac56\right)^3 = .386\ .\]

Для обчислення біноміальних ймовірностей за допомогою комп'ютера помножте функцію вибору\((n,k)\) на\(p^kq^{n - k}\). Програма binomialProbabilities виводить біноміальні ймовірності\(b(n, p, k)\) для\(k\) між\(kmin\) і\(kmax\), і суму цих ймовірностей. Ми запустили цю програму для\(n = 100\),\(p = 1/2\),\(kmin = 45\), і\(kmax = 55\); висновок наведено в таблиці 3.8. Відзначимо, що індивідуальні ймовірності досить малі. Імовірність рівно 50 голів в 100 киданнях монети становить близько 0,08. Наша інтуїція говорить нам, що це найбільш ймовірний результат, який є правильним; але, все-таки, це не дуже ймовірний результат.

Біноміальні ймовірності для\(n = 100,\ p = 1/2\).

\(k\)	\(b(n,p,k)\)
45	.0485
46	.0580
47	.0666
48	.0735
49	.0780
50	.0796
51	.0780
52	.0735
53	.0666
54	.0580
55	.0485

Біноміальні дистрибутиви

Визначення\(\PageIndex{6}\)

\(n\)Дозволяти натуральне число, і\(p\) нехай дійсне число між 0 і 1. \(B\)Дозволяти випадковою величиною, яка підраховує кількість успіхів у процесі випробувань Бернуллі з параметрами\(n\) і\(p\). Тоді\(b(n, p, k)\) розподіл\(B\) називається біноміальним розподілом.

Ми можемо отримати краще уявлення про біноміальний розподіл, побудувавши цей розподіл для різних значень\(n\) і\(p\) (див. Рис. [рис. 3.8]). Графіки на цьому малюнку були створені за допомогою програми BinomialPlot.

Ми запустили цю програму для\(p = .5\) і\(p = .3\). Відзначимо, що навіть для\(p = .3\) графіків досить симетричні. Ми матимемо пояснення цьому в главі 9. Ми також зауважимо, що найвища ймовірність виникає навколо значення\(np\), але ці найвищі ймовірності стають меншими зі\(n\) збільшенням. Ми побачимо в главі 6, що\(np\) є середнім або очікуваним значенням біноміального розподілу\(b(n,p,k)\).

Наступний приклад дає хороший спосіб побачити біноміальний розподіл, коли\(p = 1/2\).

Приклад\(\PageIndex{10}\):

Дошка Галтон - це дошка, в якій велика кількість BB-пострілів скидаються з жолоба у верхній частині дошки і відхиляються від ряду штирів на їх шляху вниз до нижньої частини дошки. Кінцеве положення кожного прорізу є результатом ряду випадкових відхилень або вліво, або вправо. Ми написали програму GaltonBoard для імітації цього експерименту.

Ми запустили програму для випадку 20 рядів шпильок та скидання 10 000 пострілів. Результат цього моделювання ми показуємо на малюнку 3.6

Зверніть увагу, що якщо ми пишемо 0 кожен раз, коли постріл відхиляється вліво, і 1 кожен раз, коли він відхиляється вправо, то шлях пострілу може бути описаний послідовністю 0 і 1 довжини\(n\), так само, як і для\(n\) -fold монети кидання.

Розподіл, показаний на малюнку 3.6, є прикладом емпіричного розподілу в тому сенсі, що воно відбувається за допомогою послідовності експериментів. Як і очікувалося, цей емпіричний розподіл нагадує відповідний біноміальний розподіл з параметрами\(n = 20\) і\(p = 1/2\).

Тестування гіпотез

Приклад\(\PageIndex{11}\):

Припустимо, що звичайний аспірин був визнаний ефективним проти головного болю 60 відсотків часу, і що лікарська компанія стверджує, що його новий аспірин зі спеціальною добавкою головного болю є більш ефективним. Ми можемо перевірити це твердження наступним чином: ми називаємо їх твердження і його заперечення, що добавка не має помітного ефекту, Таким чином, нульова гіпотеза полягає в тому\(p = .6\), і альтернативна гіпотеза полягає в\(p\) тому\(p > .6\), де ймовірність того, що новий аспірин ефективний.

Ми даємо аспірин\(n\) людям приймати, коли у них болить голова. Ми хочемо знайти число\(m\), яке називається для нашого експерименту, таке, що ми відкидаємо нульову гіпотезу, якщо хоча б\(m\) люди вилікуються, і в іншому випадку ми приймаємо її. Як ми повинні визначити це критичне значення?

По-перше, зауважте, що ми можемо зробити два види помилок. Перша, яку часто називають помилкою типу 1 в статистиці, полягає у відкиданні нульової гіпотези, коли насправді це правда. Друга, яка називається помилкою типу 2, полягає в прийнятті нульової гіпотези, коли вона хибна. Для визначення ймовірності обох цих типів помилок введено функцію\(\alpha(p)\), визначену як ймовірність того, що ми відхилимо нульову гіпотезу, де ця ймовірність обчислюється за припущенням, що нульова гіпотеза істинна. У даному випадку ми маємо\[\alpha(p) = \sum_{m \leq k \leq n} b(n,p,k)\ .\]

Відзначимо, що\(\alpha(.6)\) є ймовірність помилки типу 1, так як це ймовірність великої кількості успіхів для неефективної добавки. Таким чином, для даного\(n\) ми хочемо вибрати\(m\) так, щоб зробити\(\alpha(.6)\) зовсім невеликий, щоб зменшити ймовірність помилки типу 1. Але у міру\(m\) збільшення вище найбільш ймовірного значення\(np = .6n\)\(\alpha(.6)\), будучи верхнім хвостом біноміального розподілу, наближається до 0. Таким\(m\) чином, помилка типу 1 менш імовірна.

Тепер припустимо, що добавка дійсно ефективна, так що\(p\) це помітно більше, ніж .6; скажімо\(p = .8\). (Це\(p\) альтернативне значення вибирається довільно; наступні розрахунки залежать від цього вибору.) Тоді вибір\(m\) значно нижче\(np = .8n\) збільшиться\(\alpha(.8)\), оскільки\(\alpha(.8)\) зараз все, крім нижнього хвоста біноміального розподілу. Дійсно, якщо ми поставимо\(\beta(.8) = 1 - \alpha(.8)\), то\(\beta(.8)\) дає нам ймовірність помилки типу 2, і тому зменшення\(m\) робить помилку типу 2 менш імовірною.

Виробник хотів би вберегтися від помилки 2 типу, так як якщо така помилка допущена, то тест не показує, що новий препарат краще, коли насправді він є. Якщо\(p\) альтернативне значення вибирається ближче до значення,\(p\) заданого в нульовій гіпотезі (в даному випадку\(p =.6\)), то для даної тестової популяції значення\(\beta\) буде збільшуватися. Так, якщо статистик виробника вибирає альтернативне значення, для\(p\) якого наближена до значення в нульовій гіпотезі, то буде дорогим пропозицією (тобто тестова сукупність повинна бути великою) відхилити нульову гіпотезу з невеликим значенням\(\beta\).

Те, що ми сподіваємось зробити тоді, для даної тестової\(n\) сукупності, - це вибрати значення\(m\), якщо це можливо, що робить обидві ці ймовірності невеликими. Якщо ми робимо помилку типу 1, ми в кінцевому підсумку купуємо багато по суті звичайного аспірину за завищеною ціною; помилка типу 2 означає, що ми пропускаємо угоду на чудові ліки. Скажімо, ми хочемо,\(m\) щоб наше критичне число зробило кожен з цих небажаних випадків менш ніж 5 відсотків ймовірним.

Ми пишемо програму PowerCurve для побудови, для\(n = 100\) та вибраних\(m\) значень функції\(\alpha(p)\), для\(p\) діапазону від .4 до 1. Результат показаний на малюнку [рис. 3.9]. Ми включаємо в наш графік вікно (пунктирними лініями) від .6 до .8, з низом і зверху на висоті .05 і .95. Тоді значення для\(m\) задовольняє нашим вимогам якщо і тільки в тому випадку, якщо графа\(\alpha\) входить в поле знизу, а йде зверху (чому? —який тип 1, а який є критерієм типу 2?). У міру\(m\) збільшення графіка\(\alpha\) рухається вправо. Кілька експериментів показали нам, що\(m = 69\) це найменше значення для\(m\) того, що перешкоджає помилку типу 1, в той час як найбільша, яка\(m = 73\) перешкоджає типу 2. Таким чином, ми можемо вибрати наше критичне значення між 69 і 73. Якщо ми більше намірів уникнути помилки типу 1, ми віддаємо перевагу 73, і аналогічно ми віддаємо перевагу 69, якщо ми вважаємо помилку типу 2 гіршою. Звичайно, фармацевтична компанія може бути не задоволена тим, що має цілих 5 відсотків шансів на помилку. Вони можуть наполягати на тому, щоб мати 1 відсоток шансів на помилку. Для цього нам доведеться збільшити кількість\(n\) випробувань (див. Вправа [exer 3.2.28]).

Біноміальне розширення

Далі нагадуємо читачеві про застосування біноміальних коефіцієнтів до алгебри. Це біноміальне розширення, з якого ми отримуємо термін біноміальний коефіцієнт.

Теорема\(\PageIndex{7}\): (Binomial Theorem)

Величина\((a + b)^n\) може бути виражена у вигляді\[(a + b)^n = \sum_{j = 0}^n {n \choose j} a^j b^{n - j}\ .\] Щоб побачити, що це розширення правильне, напишіть\[(a + b)^n = (a + b)(a + b) \cdots (a + b)\ .\]

Доказ

Коли ми помножимо це, ми матимемо суму термінів, кожне з яких є результатом вибору\(a\) або\(b\) для кожного з\(n\) факторів. Коли ми вибираємо\(j\)\(a\)\((n - j)\)\(b\)'s і 's, ми отримуємо термін форми\(a^j b^{n - j}\). Щоб визначити такий термін, ми повинні вказати\(j\)\(n\) терміни в продукті, з якого ми вибираємо\(a\). Це можна зробити\(n \choose j\) способами. Таким чином, стягнення цих термінів в суму сприяє термін\({n \choose j} a^j b^{n - j}\).

Наприклад, ми маємо\[\begin{aligned} (a + b)^0 & = & 1 \\ (a + b)^1 & = & a + b \\ (a + b)^2 & = & a^2 + 2ab + b^2 \\ (a + b)^3 & = & a^3 + 3a^2b + 3ab^2 + b^3\ .\end{aligned}\] Ми бачимо тут, що коефіцієнти послідовних степенів дійсно дають трикутник Паскаля.

Слідство\(\PageIndex{1}\)

Сума елементів у\(n\) рядку трикутника Паскаля дорівнює\(2^n\). Якщо елементи в\(n\) -му рядку трикутника Паскаля додаються чергуються знаками, то сума дорівнює 0.

Доказ

Перше твердження в слідстві випливає з того, що\[2^n = (1 + 1)^n = {n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n}\ ,\] і друге з того, що\[0 = (1 - 1)^n = {n \choose 0} - {n \choose 1} + {n \choose 2}- \cdots + {(-1)^n}{n \choose n}\ .\]

Перша заява слідства говорить нам про те, що кількість підмножин безлічі\(n\) елементів дорівнює\(2^n\). Ми будемо використовувати другий твердження в нашому наступному застосуванні біноміальної теореми.

Ми бачили, що, коли\(A\) і\(B\) є будь-якими двома подіями (див. розділ [сек 1.2]),\[P(A \cup B) = P(A) + P(B) - P(A \cap B).\] Ми тепер поширюємо цю теорему на більш загальну версію, яка дозволить нам знайти ймовірність того, що принаймні одна з ряду подій відбувається.

Принцип включення-виключення

Теорема\(\PageIndex{1}\)

\(P\)Дозволяти розподіл ймовірностей на\(\Omega\) вибірковому просторі, і нехай\(\{A_1,\ A_2,\ \dots,\ A_n\}\) бути кінцевий набір подій. Потім\[P(A_1 \cup A_2 \cup \cdots \cup A_n) = \sum_{i = 1}^n P(A_i)\ - \sum_{1 \leq i < j \leq n} P(A_i \cap A_j)\]\[\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \sum_{1 \leq i < j < k \leq n} P(A_i \cap A_j \cap A_k) - \cdots\ .\label{eq 3.5}\] тобто, щоб знайти ймовірність того, що\(A_i\) відбувається хоча б одна з\(n\) подій, спочатку складають ймовірність кожної події, потім віднімають ймовірності всіх можливих двосторонніх перетинів, складають ймовірність всіх тристоронніх перетинів і так далі.

Доказ

Якщо результат\(\omega\) відбувається хоча б в одній із подій\(A_i\), його ймовірність додається рівно один раз лівою стороною Рівняння [ур. 3.5]. Ми повинні показати, що він додається рівно один раз правою стороною Рівняння [eq 3.5]. Припустимо, що\(\omega\) знаходиться в\(k\) точності з наборів. Потім його ймовірність додається\(k\) раз у першому семестрі, віднімається\(k \choose 2\) раз у другому, додається\(k \choose 3\) раз у третьому семестрі тощо. Таким чином, загальна кількість разів, що він додається,\[{k \choose 1} - {k \choose 2} + {k \choose 3} - \cdots {(-1)^{k-1}} {k \choose k}\ .\] але\[0 = (1 - 1)^k = \sum_{j = 0}^k {k \choose j} (-1)^j = {k \choose 0} - \sum_{j = 1}^k {k \choose j} {(-1)^{j - 1}}\ .\] отже,\[1 = {k \choose 0} = \sum_{j = 1}^k {k \choose j} {(-1)^{j - 1}}\ .\] Якщо результат\(\omega\) не в жодній з подій\(A_i\), то він не зараховується з обох сторін рівняння.

Проблема перевірки капелюха

Приклад\(\PageIndex{1}\):

Повертаємося до проблеми перевірки капелюхів, розглянутої в розділі 1.1, тобто до проблеми знаходження ймовірності того, що випадкова перестановка містить хоча б одну фіксовану точку. Нагадаємо, що перестановка - це карта «один на один» набору\(A = \{a_1,a_2,\dots,a_n\}\) на себе. Нехай\(A_i\) буде подія, що\(i\) той елемент\(a_i\) залишається закріпленим під цією картою. Якщо ми вимагаємо,\(a_i\) що закріплено, то карта інших\(n - 1\) елементів передбачає довільну перестановку\((n - 1)\) об'єктів. Так як є\((n - 1)!\) такі перестановки,\(P(A_i) = (n - 1)!/n! = 1/n\). Оскільки існує\(n\) вибір\(a_i\), перший член Рівняння [ур. 3.5] дорівнює 1. Таким же чином, щоб мати певну пару\((a_i,a_j)\) фіксованою, ми можемо вибрати будь-яку перестановку решти\(n - 2\) елементів; є\((n - 2)!\) такі варіанти, і, отже\[P(A_i \cap A_j) = \frac{(n - 2)!}{n!} = \frac 1{n(n - 1)}\ .\], кількість членів цієї форми в правій частині Рівняння [eq 3.5]\[{n \choose 2} = \frac{n(n - 1)}{2!}\ .\] Отже, другий член Рівняння [Eq 3.5]\[-\frac{n(n - 1)}{2!} \cdot \frac 1{n(n - 1)} = -\frac 1{2!}\ .\] Аналогічно, для будь-яких конкретних трьох подій\(A_i\)\(A_j\)\(A_k\),,\[P(A_i \cap A_j \cap A_k) = \frac{(n - 3)!}{n!} = \frac 1{n(n - 1)(n - 2)}\ ,\] і кількість таких членів\[{n \choose 3} = \frac{n(n - 1)(n - 2)}{3!}\ ,\] робить третій член рівняння [eq 3.5] рівним 1/3!. Продовжуючи таким чином, ми отримуємо\[P(\mbox {at\ least\ one\ fixed\ point}) = 1 - \frac 1{2!} + \frac 1{3!} - \cdots (-1)^{n-1} \frac 1{n!}\] і\[P(\mbox {no\ fixed\ point}) = \frac 1{2!} - \frac 1{3!} + \cdots (-1)^n \frac 1{n!}\ .\]

З числення ми дізнаємося, що\[e^x = 1 + x + \frac 1{2!}x^2 + \frac 1{3!}x^3 + \cdots + \frac 1{n!}x^n + \cdots\ .\] Таким чином\(x = -1\), якщо, ми маємо\[\begin{aligned} e^{-1} & = &\frac 1{2!} - \frac 1{3!} + \cdots + \frac{(-1)^n}{n!} + \cdots \\ & = & .3678794\ .\end{aligned}\] Тому ймовірність того, що немає фіксованої точки, тобто, що ніхто з\(n\) людей не отримує свою шапку назад, дорівнює сумі перших\(n\) членів у виразі для\(e^{-1}\). Цей ряд сходиться дуже швидко. Розрахунок часткових сум для\(n = 3\) до 10 дають дані в таблиці [табл. 3.7].

Проблема перевірки капелюха.

	Ймовірність того, що ніхто
п	отримує свій власний капелюх назад
3	.3333
4	.375
5	.366667
6	.368056
7	.367857
8	.367882
9	.367879
10	.367879

Адже\(n = 9\) ймовірності по суті однакові до шести значущих цифр. Цікаво, що ймовірність відсутності фіксованої точки по черзі збільшується і зменшується зі\(n\) збільшенням. Нарешті, ми зауважимо, що наші точні результати добре узгоджуються з нашими моделюваннями, повідомленими в попередньому розділі.

Вибір місця для зразків

Тепер у нас є деякі інструменти, необхідні для точного опису проб просторів та призначення функцій ймовірності цим просторам вибірки. Проте в деяких випадках процес опису і присвоєння кілька умовний. Звичайно, слід сподіватися, що опис простору вибірки та подальше призначення функції ймовірності дасть модель, яка точно прогнозує, що станеться, якби експеримент був фактично проведений. Як показують наведені нижче приклади, існують ситуації, коли «розумні» описи простору вибірки не дають моделі, яка відповідає даним.

У книзі Феллера ¹⁴ наведено пару моделей, які описують розташування певних видів елементарних частинок, таких як фотони та протони. Виявляється, експерименти показали, що певні типи елементарних частинок демонструють поведінку, яка точно описується однією моделлю, яка називається, тоді як інші типи елементарних частинок можуть бути змодельовані за допомогою Феллера каже:

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

Зараз ми наведемо кілька прикладів цього опису і процесу присвоєння.

Приклад\(\PageIndex{13}\):

У квантово-механічній моделі атома гелію для класифікації енергетичних станів атома можуть використовуватися різні параметри. У стані триплетного спина (\(S = 1\)) з орбітальним моментом 1 (\(L = 1\)) існує три можливості, 0, 1 або 2, для загального кутового імпульсу (\(J\)). (Не передбачається, що читач знає, що будь-яке з цього означає; насправді приклад є більш показовим, якщо читач знає що-небудь про квантову механіку.) Ми хотіли б призначити ймовірності трьом можливостям для\(J\). Читач, безсумнівно, чинить опір ідеї присвоєння\(1/3\) ймовірності кожному з цих результатів. Тепер вона повинна запитати себе, чому вона чинить опір цьому дорученню. Відповідь, ймовірно, тому, що у неї немає ніякої «інтуїції» (тобто досвіду) щодо того, як поводяться атоми гелію. Насправді в даному\(1/9,\ 3/9,\) прикладі ймовірності і\(5/9\) присвоюються теорією. Теорія дає ці завдання, оскільки ці частоти спостерігалися і подальші параметри були розроблені в теорії, щоб дозволити прогнозувати ці частоти.

Приклад\(\PageIndex{14}\):

Припустимо, дві копійки перевертаються один раз кожен. Існує кілька «розумних» способів опису простору вибірки. Один із способів - підрахувати кількість голів в результаті; в цьому випадку можна записати простір зразка\(\{0, 1, 2\}\). Іншим описом простору вибірки є сукупність всіх впорядкованих\(H\) пар\(T\)'s і's, тобто\[\{(H,H), (H, T), (T, H), (T, T)\}.\] обидва ці опису є точними, але легко помітити, що (максимум) один з них, якщо йому присвоєна функція постійної ймовірності, може претендувати на точне моделювання реальності. У цьому випадку, на відміну від попереднього прикладу, читач, ймовірно, скаже, що другий опис, при якому кожному результату присвоюється ймовірність\(1/4\), є «правильним» описом. Це переконання пов'язано з досвідом; немає доказів того, що саме так працює реальність.

Читач також посилається на Вправу 26 для іншого прикладу цього процесу.

Історичні зауваження

Біноміальні коефіцієнти мають довгу та барвисту історію, що веде до Трактату Паскаля про арифметичний трикутник ¹⁵, де Паскаль розробив багато важливих властивостей цих чисел. Ця історія викладена в книзі Арифметичного трикутника Паскаля О.Ф. Едвардса. ¹⁶ Паскаль написав свій трикутник у вигляді, наведеному в таблиці 3.10.

Запишіть 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 8 & 9 1 & 3 & 9 1 & 3 & 6 & 6 & 10 & 15 & 21 & 28 & 36 1 & 4 & 10 & 20 & 35 & 56 & 84 1 & 5 & 15 & 35 & підсилювач; 70 & 126 1 & 6 & 21 & 56 &126 1 & 7 & 28 & 84 1 & 8 & 36 1 & 9 1

Едвардс простежує три різні способи виникнення біноміальних коефіцієнтів. Він називає їх фігурними числами, комбінаторними числами та біноміальними числами. Всі вони є іменами для одного і того ж (які ми назвали біноміальними коефіцієнтами), але те, що вони всі однакові, не оцінювалося до шістнадцятого століття.

Фігурні числа датуються інтересом Піфагора до числових моделей близько 540. Піфагорійці розглядали, наприклад, трикутні візерунки, показані на малюнку 3.8. Послідовність чисел,\[1, 3, 6, 10, \dots\] отриманих у вигляді кількості точок в кожному трикутнику, називається трикутними числами. З трикутників зрозуміло, що трикутне число - це просто сума перших\(n\) цілих чисел.\(n\) Чотиригранні числа є сумами трикутних чисел і були отримані грецькими математиками Теоном і Нікомахом на початку другого століття. Наприклад, чотиригранне число 10 має геометричне зображення, показане на малюнку 3.9. Перші три види фігурних чисел можна представити в табличній формі, як показано в таблиці 3.11.

\[\begin{array}{llllllllll} \mbox {natural\ numbers} & 1\hskip.2in & 2\hskip.2in & 3\hskip.2in & 4\hskip.2in & 5\hskip.2in & 6\hskip.2in & 7\hskip.2in & 8\hskip.2in & 9 \cr \mbox {triangular\ numbers} & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 \cr \mbox {tetrahedral\ numbers}& 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 &165 \end{array}\]

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

На Сході індуїстські математики почали стикатися з біноміальними коефіцієнтами в комбінаторних задачах. Бхаскара в своєму 1150 році дав правило знаходити кількість лікарських препаратів з використанням 1, 2, 3, 4, 5 або 6 можливих інгредієнтів. ¹⁷ Його правило еквівалентно нашій формулі\[{n \choose r} = \frac{(n)_r}{r!}\ .\]

Біноміальні числа як коефіцієнти\((a + b)^n\) з'явилися в працях математиків Китаю близько 1100. Є згадки про цей час на «систему табуляції для розблокування біноміальних коефіцієнтів». Трикутник для забезпечення коефіцієнтів до восьмого ступеня задається Чу Ші-чіе в книзі, написаній близько 1303 (див. Рис. ¹⁸ Оригінальний рукопис книги Чу був втрачений, але копії збереглися. Едвардс зазначає, що в цій копії трикутника Чу є помилка. Чи можете ви його знайти? (: Два числа, які повинні бути рівними, не є.) Інші копії не показують цю помилку.

Перша поява трикутника Паскаля на Заході, здається, походить від розрахунків Тарталії при обчисленні кількості можливих способів, які можуть з'явитися\(n\) кістки. ¹⁹ Бо одна вмирає відповідь явно 6. Для двох кубиків можливості можуть відображатися, як показано в таблиці [табл. 3.10].

\[\matrix{ 11\cr 12 & 22\cr 13 & 23 & 33\cr 14 & 24 & 34 & 44\cr 15 & 25 & 35 & 45 & 55\cr 16 & 26 & 36 & 46 & 56 & 66\ \cr }\]

Відображення їх таким чином передбачає шосте трикутне число\(1 + 2 + 3 + 4 + 5 + 6 = 21\) для кидка 2 кубиків. Тарталья «в перший день Великого посту, 1523 року, у Вероні, задумавшись над проблемою всю ніч» ²⁰ зрозумів, що розширення фігурної таблиці дає відповіді на\(n\) кубики. Проблема запропонувала Тарталії спостерігати за тим, як люди кидають свої власні гороскопи за допомогою Книги Фортуни, вибираючи вірші шляхом процесу, який включав відзначаючи цифри на обличчях трьох кубиків. 56 способів падіння трьох кубиків були викладені на кожній сторінці. Те, як цифри були написані в книзі, не припускав зв'язку з фігурними числами, але метод перерахування, подібний до того, який ми використовували для 2 кубиків робить. Таблиця Тарталья не була опублікована до 1556 року.

Таблиця для біноміальних коефіцієнтів була опублікована в 1554 році німецьким математиком Штіфелем. ²¹ Трикутник Паскаля з'являється також у Cardano 1570 року. ²² Cardano цікавилася проблемою пошуку кількості способів вибору\(r\) об'єктів з\(n\). Таким чином, до моменту роботи Паскаля його трикутник з'явився в результаті погляду на фігурні числа, комбінаторні числа та біноміальні числа, і той факт, що всі три були однаковими, мабуть, досить добре зрозумілий.

Зацікавленість Паскаля до біноміальних чисел випливає з його листів з Ферматом щодо проблеми, відомої як проблема точок. Ця проблема та відповідність між Паскалем і Ферма обговорювалися в главі 1. Читач нагадає, що цю проблему можна описати так: Два гравця A і B грають послідовність ігор і перший гравець, який виграв\(n\) ігри, виграє матч. Бажано знайти ймовірність того, що А виграє матч в той час, коли А виграв\(a\) ігри, а Б виграв\(b\) ігри. (Див. Вправи 4.1.40-4.1.42.)

Паскаль вирішив проблему зворотною індукцією, так само, як ми зробили б сьогодні при написанні комп'ютерної програми для її вирішення. Він посилався на комбінаторний метод Ферма, який триває наступним чином: Якщо A потрібні\(c\) ігри, а B потрібні\(d\) ігри, щоб виграти, ми вимагаємо, щоб гравці продовжували грати, поки вони не грали в\(c + d - 1\) ігри. Переможець у цій розширеній серії буде таким же, як і переможець в оригінальній серії. Імовірність того, що A виграє в розширеній серії, а отже, і в оригінальній серії, є\[\sum_{r = c}^{c + d - 1} \frac 1{2^{c + d - 1}} {{c + d - 1} \choose r}\ .\] Навіть під час букв Паскаль, здавалося, зрозумів цю формулу.

Припустимо, що перший гравець, який виграв\(n\) ігри, виграє матч, і припустимо, що кожен гравець поставив частку\(x\). Паскаль вивчав цінність перемоги в тій чи іншій грі. Під цим він мав на увазі збільшення очікуваного виграшу переможця конкретної даної гри. Він показав, що значення першої гри є\[\frac {1\cdot3\cdot5\cdot\dots\cdot(2n - 1)}{2\cdot4\cdot6\cdot\dots\cdot(2n)}x\ .\] Його доказом цього, здається, використовується формула Ферма і той факт, що наведене вище співвідношення добутків непарних до добутків парних чисел дорівнює ймовірності точно\(n\) голів в\(2n\) киданнях монети. (Див. Вправу 39.)

Паскаль представив Ферма таблицю, наведену в таблиці 3.13

Рішення Паскаля для проблеми очок.

З 256 мого опонента	6	5	4	3	2	1
позиції, які я отримую, для	ігри	ігри	ігри	ігри	ігри	ігри
1-а гра	63	70	80	96	128	256
2-а гра	63	70	80	96	128
3-тя гра	56	60	64	64
4-а гра	42	40	32
5-а гра	24	16
6-а гра

Він заявляє:

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

Студент може продовжувати це питання далі, використовуючи комп'ютер і метод зворотної ітерації Паскаля для обчислення очікуваного виграшу в будь-якій точці серії.

У своєму трактаті Паскаль дав формальний доказ комбінаторної формули Ферма, а також докази багатьох інших основних властивостей біноміальних чисел. Багато з його доказів передбачали індукцію і являють собою деякі з перших доказів цим методом. Його книга об'єднала всі різні аспекти чисел у трикутнику Паскаля, як відомо в 1654 році, і, як стверджує Едвардс, «Те, що арифметичний трикутник повинен носити ім'я Паскаля, не можна оскаржувати». ²⁴

Перше серйозне дослідження біноміального розподілу було здійснено Джеймсом Бернуллі в його опублікованому в 1713 році. ²⁵ Ми повернемося до цієї роботи в історичних зауваженнях у главі 8.

Вправи

\(\PageIndex{1}\)Обчисліть наступне:

1. \({6 \choose 3}\)

2. \(b(5,.2,4)\)

3. \({7 \choose 2}\)

4. \(
   ParseError: EOF expected (click for details)

   Callstack:
       at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.02:_Комбінації), /content/body/div[14]/ol[1]/li[4]/span/span, line 1, column 3
   

   \)

5. \(b(4,.2,3)\)

6. \({6 \choose 2}\)

7. \({{10} \choose 9}\)

8. \(b(8, .3, 5)\)

\(\PageIndex{2}\)Скільки способів ми можемо вибрати п'ять осіб з групи з десяти для формування комітету?

\(\PageIndex{3}\)Скільки сім-елементних підмножин існує в наборі з дев'яти елементів?

\(\PageIndex{4}\)Використовуючи відношення Equation 3.1 написати програму для обчислення трикутника Паскаля, помістивши результати в матрицю. Нехай ваша програма надрукує трикутник для\(n = 10\).

\(\PageIndex{5}\)Використовуйте програму BinomialProbabilities, щоб знайти ймовірність того, що в 100 киданнях справедливої монети кількість голів, яка виявляється, лежить між 35 і 65, між 40 і 60, і між 45 і 55.

\(\PageIndex{6}\)Чарльз стверджує, що він може відрізняти пиво від елю 75 відсотків часу. Рут робить ставку, що не може і, по суті, просто здогадується. Щоб врегулювати це, робиться ставка: Чарльзу потрібно дати десять маленьких келихів, кожен з яких був наповнений пивом або елем, обраний шляхом кидання справедливої монети. Він виграє ставку, якщо отримає сім і більше правильних. Знайдіть ймовірність того, що Чарльз виграє, якщо у нього є здібності, які він стверджує. Знайдіть ймовірність того, що Рут виграє, якщо Чарльз ворожить.

\(\PageIndex{7}\)Покажіть, що\[b(n,p,j) = \frac pq \left(\frac {n - j + 1}j \right) b(n,p,j - 1)\ ,\] для\(j \ge 1\). Використовуйте цей факт, щоб визначити значення або значення\(j\), які дають\(b(n,p,j)\) його найбільше значення.: Розглянемо послідовні співвідношення як\(j\) збільшення.

\(\PageIndex{8}\)Плашка прокочується 30 разів. Яка ймовірність того, що 6 виходить рівно в 5 разів? Яка найімовірніша кількість разів, що 6 з'явиться?

\(\PageIndex{9}\)Знайдіть цілі числа\(n\) і\(r\) такі, що таке рівняння відповідає дійсності:\[{13 \choose 5} + 2{13 \choose 6} + {13 \choose 7} = {n \choose r}\ .\]

\(\PageIndex{10}\)У десяти питаннях істинно-помилковий іспит знайдіть ймовірність того, що студент отримує оцінку 70 відсотків або краще, вгадавши. Дайте відповідь на те ж питання, якщо тест має 30 питань, і якщо тест має 50 питань.

\(\PageIndex{11}\)Ресторан пропонує яблучні і чорничні пироги і запаси рівну кількість кожного виду пирога. Щодня десять клієнтів просять пиріг. Вони вибирають з однаковою ймовірністю один з двох видів пирога. Скільки шматочків кожного виду пирога повинен надати власник, щоб ймовірність становила близько .95, що кожен клієнт отримає пиріг за власним вибором?

\(\PageIndex{12}\)Покерна рука - це набір з 5 карт, випадково обраних з колоди з 52 карт. Знайти ймовірність

1. роял флеш (десятка, валет, дама, король, туз в єдиній масті).

2. стрит-флеш (п'ять в послідовності в одній масті, але не королівський флеш).

3. чотири виду (чотири карти однакового номіналу).

4. фул-хаус (одна пара і одна тримісна, кожен однакового номіналу).

5. флеш (п'ять карт в одній масті, але не стрит або королівський флеш).

6. пряма (п'ять карт в послідовності, не всі однакові масті). (Зверніть увагу, що в прямих туз рахується високим або низьким.)

\(\PageIndex{13}\)Якщо набір має\(2n\) елементи, показати, що він має більше підмножин з\(n\) елементами, ніж з будь-якою іншою кількістю елементів.

\(\PageIndex{14}\)Нехай\(b(2n,.5,n)\) буде ймовірність того, що в\(2n\) підкиданнях справедливої монети точно\(n\) піднімаються голови. Використовуючи формулу Стірлінга (теорема 3.1), показати, що\(b(2n,.5,n) \sim 1/\sqrt{\pi n}\). Використовуйте програму BinomialProbabilities, щоб порівняти це з точним значенням\(n = 10\) до 25.

\(\PageIndex{15}\)Бейсболіст, Сміт, має ватин середній\(.300\) і в типовій грі приходить битою три рази. Припустімо, що хіти Сміта в грі можна вважати процесом випробувань Бернуллі з ймовірністю .3 для Знайдіть ймовірність того, що Сміт отримає 0, 1, 2 та 3 хіти.

\(\PageIndex{16}\)Футбольна команда університету Сіваш грає вісім ігор в сезоні, вигравши три, програвши три, і закінчуючи два в нічию. Покажіть, що кількість способів, якими це може статися, є\[{8 \choose 3}{5 \choose 3} = \frac {8!}{3!\,3!\,2!}\ .\]

\(\PageIndex{17}\)Використовуючи техніку вправи 16, покажіть, що кількість способів, якими можна помістити\(n\) різні предмети\(a\) в три коробки з\(b\) в першому, в другому і\(c\) в третьому є\(n!/(a!\,b!\,c!)\).

\(\PageIndex{18}\)Баумгартнер, Проссер і Кроуелл оцінюють іспит з обчислення. Існує правдиво-помилкове питання з десятьма частинами. Баумгартнер зауважує, що один студент має лише два з десяти правильних і зауважень: «Студент був навіть недостатньо яскравим, щоб перевернути монету, щоб визначити свої відповіді». «Не так зрозуміло», - каже Проссер. «З 340 студентами я впевнений, що якщо вони всі перевернули монети, щоб визначити свої відповіді, буде принаймні один іспит з двома або меншими відповідями правильними». Кроуелл каже: «Я з Проссером. Насправді, я впевнений, що ми повинні очікувати хоча б одного іспиту, на якому жодна відповідь не є правильною, якщо всі просто здогадуються». Хто має рацію у всьому цьому?

\(\PageIndex{19}\)Джин-рука складається з 10 карт з колоди з 52 карт. Знайдіть ймовірність того, що у джин-руки

1. всі 10 карт однієї масті.

2. рівно 4 карти в одній масті і 3 в двох інших мастях.

3. а 4, 3, 2, 1, розподіл мастей.

\(\PageIndex{20}\)Шестикарткова рука роздається зі звичайної колоди карт. Знайдіть ймовірність того, що:

1. Всі шість карт - це серця.

2. Є три тузи, два королі, і одна королева.

3. Є три карти однієї масті і три іншої масті.

\(\PageIndex{21}\)Дама бажає пофарбувати нігті на одній руці, використовуючи щонайбільше два кольори: червоний, жовтий та синій. Скільки способів вона може це зробити?

\(\PageIndex{22}\)Скільки способів можна помістити шість нерозрізнених листів в три поштові скриньки? : Одне представлення цього задається послідовністю\(|\) LL\(|\) L\(|\) LLL,\(|\) де ті\(|\) представляють розділи для ящиків, а букви L. Будь-який можливий спосіб можна так описати. Зверніть увагу, що нам потрібні дві планки на кінцях, а решта два бруска і шість L можна поставити в будь-якому порядку.

\(\PageIndex{23}\)Використовуючи метод для підказки у\(r\) Вправі 22, покажіть, що нерозрізнені предмети можна класти в\(n\) ящики\[

ParseError: EOF expected (click for details)

Callstack:
    at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.02:_Комбінації), /content/body/div[14]/p[23]/span[4]/span, line 1, column 10

= {{n + r - 1} \choose r}\] по-різному.

\(\PageIndex{24}\)Туристичне бюро підраховує, що коли 20 туристів їдуть на курорт з десятьма готелями, вони розподіляють себе так, ніби бюро кладе 20 невиразних предметів у десять помітних коробок. Припускаючи, що ця модель вірна, знайдіть ймовірність того, що жоден готель не залишиться вакантним, коли приїде перша група з 20 туристів.

\(\PageIndex{25}\)Ліфт приймає шість пасажирів і зупиняється на десяти поверхах. Ми можемо призначити дві різні рівноймовірні заходи для способів звільнення пасажирів: (а) ми вважаємо пасажирів помітними або (б) вважаємо їх нерозрізненими (див. Вправа 23 для цього випадку). Для кожного випадку розрахуйте ймовірність того, що всі пасажири зійдуть на різних поверхах.

\(\PageIndex{26}\)Ви граєте з Prosser, але ви підозрюєте, що його монета несправедлива. Фон Нейман запропонував вам поступити наступним чином: двічі киньте монету Проссера. Якщо результат - HT, викликайте результат, якщо це TH, викликайте результат Якщо це TT або HH, ігноруйте результат і знову киньте монету Проссера двічі. Продовжуйте йти, поки ви не отримаєте або HT або TH і називаєте результат виграш або програєте в одній грі. Повторюйте цю процедуру для кожної п'єси. Припустимо, що монета Проссера повертає голови з ймовірністю\(p\).

1. Знайдіть ймовірність HT, TH, HH, TT з двома кидками монети Проссера.

2. Використовуючи частину (а), покажіть, що ймовірність виграшу в будь-якій грі становить 1/2, незалежно від того, що\(p\) є.

\(\PageIndex{27}\)Джон стверджує, що він має екстрасенсорні повноваження і може сказати, який з двох символів знаходиться на карті, повернутій обличчям вниз (див. Приклад 12). Щоб перевірити свої здібності, його просять зробити це для послідовності випробувань. Нехай нульова гіпотеза полягає в тому, що він просто здогадується, так що ймовірність становить 1/2 його отримання правильно кожен раз, і нехай альтернативна гіпотеза полягає в тому, що він може назвати символ правильно більше половини часу. Розробіть тест із властивістю, що ймовірність помилки типу 1 менше 0,05 і ймовірність помилки типу 2 менше 0,05, якщо Джон може правильно назвати символ 75 відсотків часу.

\(\PageIndex{28}\)У\(p = .8\) прикладі\(\PageIndex{12}\) припустимо, що альтернативна гіпотеза полягає в тому, що і що бажано мати ймовірність кожного типу помилки менше 0,01. Використовуйте програму PowerCurve для визначення значень\(n\) і\(m\) що дозволить досягти цього. Вибирайте\(n\) якомога менше.

\(\PageIndex{29}\)Препарат вважається ефективним з невідомою ймовірністю\(p\). Для оцінки\(p\) препарат дають\(n\) пацієнтам. Виявлено, що він ефективний для\(m\) пацієнтів. Для оцінки\(p\) стану, що ми повинні вибрати значення для\(p\) цього дає найбільшу ймовірність отримати те, що ми отримали на експерименті. Припускаючи, що експеримент можна розглядати як процес випробувань Бернуллі з ймовірністю\(p\) для успіху, показують, що максимальна оцінка ймовірності\(p\) - це частка\(m/n\) успіхів.

\(\PageIndex{30}\)Нагадаємо, що в Світовій серії перша команда, яка виграла чотири ігри, виграє серію. Серія може пройти максимум сім ігор. Припустимо, що Ред Сокс і Метс грають серію. Припустимо, що «Метс» виграють кожну гру з ймовірністю\(p\). Фермат зауважив, що, незважаючи на те, що серія може не пройти сім ігор, ймовірність того, що Метс виграють серію така ж, як ймовірність того, що вони виграють чотири або більше гри в серії, яка була змушена пройти сім ігор незалежно від того, хто виграє окремі ігри.

1. За допомогою програми PowerCurve Прикладу 3.11 знайдіть ймовірність того, що Мец виграє серію для випадків\(p = .5\)\(p = .6\),\(p =.7\).

2. Припустимо, що Метс має ймовірність 0.6 перемоги в кожній грі. Використовуйте програму PowerCurve, щоб знайти значення,\(n\) щоб, якщо серія перейде до першої команди, щоб виграти більше половини ігор, Метс матиме 95-відсотковий шанс виграти серію. Вибирайте\(n\) якомога менше.

\(\PageIndex{31}\)] Кожен з чотирьох двигунів на літаку правильно функціонує на заданому польоті з ймовірністю .99, і двигуни функціонують незалежно один від одного. Припустимо, що літак може здійснити безпечну посадку, якщо хоча б два його двигуни функціонують правильно. Яка ймовірність того, що двигуни дозволять здійснити безпечну посадку?

\(\PageIndex{32}\)Маленький хлопчик втрачається, спускаючись з гори Вашингтон. Лідер пошукової групи підраховує, що є ймовірність\(p\) того, що він зійшов на східну сторону і ймовірність\(1 - p\) того, що він зійшов на західну сторону. У його пошуковій команді є\(n\) люди, які будуть шукати самостійно, і, якщо хлопчик знаходиться на стороні, яку шукають, кожен член з ймовірністю знайде хлопчика\(u\). Визначте, як він повинен розділити\(n\) людей на дві групи, щоб обшукати дві сторони гори, щоб у нього була найвища ймовірність знайти хлопчика. Від чого це залежить\(u\)?

\(*\PageIndex{33}\)\(2n\)кулі вибираються навмання із загальної кількості\(2n\) червоних куль і\(2n\) синіх куль. Знайдіть комбінаторний вираз для ймовірності того, що обрані кульки розділені порівну за кольором. Скористайтеся формулою Стірлінга, щоб оцінити цю ймовірність. Використовуючи біноміальніймовірності, порівняйте точне значення з наближенням Стірлінга для\(n = 20\).

\(\PageIndex{34}\)Припустимо, що кожен раз, коли ви купуєте коробку пшениці, ви отримуєте одну з фотографій\(n\) гравців на «Нью-Йорк Янкіз». Протягом певного періоду часу ви купуєте\(m \geq n\) коробки пшениці.

1. Використовуйте теорему 3.8, щоб показати, що ймовірність того, що ви отримаєте всі\(n\) фотографії\[\begin{aligned} 1 &-& {n \choose 1} \left(\frac{n - 1}n\right)^m + {n \choose 2} \left(\frac{n - 2}n\right)^m - \cdots \\ &+& (-1)^{n - 1} {n \choose {n - 1}}\left(\frac 1n \right)^m.\end{aligned}\]: Нехай\(E_k\) буде подія, що ви не отримаєте фотографію гравця.\(k\)

2. Напишіть комп'ютерну програму для обчислення цієї ймовірності. Використовуйте цю програму, щоб знайти, для заданого\(n\), найменше значення\(m\) якого дасть ймовірність\(\geq .5\) отримання всіх\(n\) знімків. Розглянемо\(n = 50\), 100, і 150 і показати, що\(m = n\log n + n \log 2\) це хороша оцінка для кількості ящиків, необхідних. (Для виведення цієї оцінки див. Феллер. ²⁶)

\(\PageIndex{35}\)Доведіть наступну біноміальну ідентичність

\[{2n \choose n} = \sum_{j = 0}^n { n \choose j}^2\ .\]: Розглянемо урну з\(n\) червоними кульками і\(n\) синіми кульками всередині. Покажіть, що кожна сторона рівняння дорівнює кількості способів вибору\(n\) кульок з урни.

\(\PageIndex{36}\)\(n\)Дозволяти\(j\) і бути натуральними числами, з\(j \le n\). Експеримент складається з вибору\(j\) випадкового кортежу цілих чисел, сума яких не більше\(n\).

1. Знайдіть розмір простору зразка.: Розглянемо\(n\) нерозрізнені кульки, розміщені в ряд. \(j\)Розміщуйте маркери між послідовними парами куль, не маючи двох маркерів між однією парою куль. (Ми також дозволяємо розмістити один з\(n\) маркерів в кінці ряду куль.) Показати, що існує відповідність 1-1 між набором можливих позицій для маркерів і набором\(j\) -кортежів, розмір яких ми намагаємося порахувати.

2. Знайти ймовірність того, що вибраний\(j\) -кортеж містить принаймні один 1.

\(\PageIndex{37}\)Нехай\(n\ (\mbox{mod}\ m)\) позначають залишок, коли ціле число\(n\) ділиться на ціле число\(m\). Напишіть комп'ютерну програму для обчислення чисел,\({n \choose j}\ (\mbox{mod}\ m)\) де\({n \choose j}\) є біноміальним коефіцієнтом і\(m\) є цілим числом. Зробити це можна за допомогою рекурсійних відносин для генерації біноміальних коефіцієнтів, виконуючи всю арифметику за допомогою базової функції mod (\(n,m\)). Спробуйте написати свою програму, щоб зробити якомога більшу таблицю. Запустіть програму для випадків\(m = 2\) до 7. Ви бачите якісь візерунки? Зокрема, для випадку\(m = 2\) і степені\(n\) 2 перевірте, що всі записи в\((n - 1)\) 1-му рядку дорівнюють 1. (Відповідні біноміальні числа непарні.) Використовуйте свої фотографії, щоб пояснити, чому це правда.

\(\PageIndex{38}\)Лукас ²⁷ довів наступний загальний результат, що стосується вправи 37. Якщо будь-яке\(p\) просте число, то\({n \choose j}~ (\mbox{mod\ }p)\) можна знайти наступним чином: Expand\(n\) і\(j\) in base\(p\) as\(n = s_0 + s_1p + s_2p^2 + \cdots + s_kp^k\) і\(j = r_0 + r_1p + r_2p^2 + \cdots + r_kp^k\), відповідно. (Тут\(k\) вибирається досить великий, щоб представляти всі числа від 0 до\(n\) основи,\(p\) використовуючи\(k\) цифри.) Нехай\(s = (s_0,s_1,s_2,\dots,s_k)\) і\(r = (r_0,r_1,r_2,\dots,r_k)\). Тоді\[{n \choose j}~(\mbox{mod\ }p) = \prod_{i = 0}^k

ParseError: EOF expected (click for details)

Callstack:
    at (Статистика/Теорія_ймовірностей/Книга:_Вступна_ймовірність_(Grinstead_і_Snell)/03:_Комбінаторика/3.02:_Комбінації), /content/body/div[14]/p[39]/span[15]/span, line 1, column 4

~(\mbox{mod\ }p)\ .\] Наприклад, якщо\(p = 7\)\(n = 12\), і\(j = 9\), то

\[\begin{aligned} 12 & = & 5 \cdot 7^0 + 1 \cdot 7^1\ , \\ 9 & = & 2 \cdot 7^0 + 1 \cdot 7^1\ , \end{aligned}\]так що\[\begin{aligned} s & = & (5, 1)\ , \\ r & = & (2, 1)\ , \end{aligned}\] і цей результат стверджує, що\[{12 \choose 9}~(\mbox{mod\ }p) = {5 \choose 2} {1 \choose 1}~(\mbox{mod\ }7)\ .\] Оскільки\({12 \choose 9} = 220 = 3~(\mbox{mod\ }7)\), і\({5 \choose 2} = 10 = 3~ (\mbox{mod\ }7)\), ми бачимо, що результат правильний для цього прикладу.

Покажіть, що цей результат означає, що для\(p = 2\),\((p^k - 1)\) перший рядок вашого трикутника у Вправі 37 не має нулів.

\(\PageIndex{39}\)Довести, що ймовірність точно\(n\) голови в\(2n\) кидки справедливої монети задається добутком непарних чисел до\(2n - 1\) ділиться на добуток парних чисел до\(2n\).

\(\PageIndex{40}\)\(n\)Дозволяти натуральне число, і припустимо, що\(j\) це додатне число, що не перевищує\(n/2\). Показати, що в теоремі 3.5, якщо чергувати множення і ділення, то всі проміжні значення в обчисленні є цілими числами. Показати також, що жодне з цих проміжних значень не перевищує кінцевого значення.