3.1: Перестановки

Багато проблем теорії ймовірностей вимагають, щоб ми підрахували кількість способів, якими може статися та чи інша подія. Для цього вивчаємо теми перестановок і комбінацій. Розглянемо перестановки в цьому розділі і комбінації в наступному розділі. Перш ніж обговорювати перестановки, корисно ввести загальну методику підрахунку, яка дозволить нам вирішити різноманітні задачі підрахунку, включаючи проблему підрахунку кількості можливих перестановок$n$ об'єктів.

Проблеми підрахунку

Розглянемо експеримент, який проходить в кілька етапів і такий, що кількість результатів$m$ на$n$ -му етапі не залежить від результатів попередніх етапів. Кількість$m$ може бути різною для різних етапів. Ми хочемо порахувати кількість способів, якими може бути проведений весь експеримент.

Приклад$\PageIndex{1}$

Ви їсте в ресторані Émile, і офіціант повідомляє вам, що у вас є (а) два варіанти закусок: суп або сік; (б) три для основної страви: м'ясо, риба або овочеве блюдо; і (в) два на десерт: морозиво або торт. Скільки можливих варіантів у вас є для повноцінного харчування? Ми ілюструємо можливі страви за допомогою діаграми дерева, показаної на малюнку.$\PageIndex{1}$ Ваше меню вирішується в три етапи — на кожному етапі кількість можливих варіантів не залежить від того, що було вибрано на попередніх етапах: два варіанти на першому етапі, три на другому і два на третьому. З діаграми дерева ми бачимо, що загальна кількість варіантів є добутком кількості варіантів на кожному етапі. У цих прикладах у нас є$2 \cdot 3 \cdot 2 = 12$ можливі меню. Наш приклад меню є прикладом наступної загальної техніки підрахунку.

A Метод підрахунку

Завдання має виконуватися в послідовності$r$ етапів. Існують$n_1$ способи проведення першого етапу; для кожного з цих$n_1$$n_2$ способів існують способи проведення другого етапу; для кожного з цих$n_2$$n_3$ способів існують способи проведення третього етапу тощо. Потім загальна кількість способів, за допомогою яких може бути виконана вся задача, задається продуктом$N = n_1 \cdot n_2 \cdot \dots \cdot n_r$.

Деревовидні діаграми

Часто буде корисно використовувати деревоподібну діаграму при вивченні ймовірностей подій, що стосуються експериментів, які відбуваються поетапно і для яких нам даються ймовірності результатів на кожному етапі. Наприклад, припустимо, що власник ресторану Еміля зауважив, що 80 відсотків його клієнтів вибирають суп для закуски, а 20 відсотків вибирають сік. З тих, хто вибирає суп, 50 відсотків вибирають м'ясо, 30 відсотків вибирають рибу, а 20 відсотків вибирають овочеве блюдо. З тих, хто вибирає сік для закуски, 30 відсотків вибирають м'ясо, 40 відсотків вибирають рибу, а 30 відсотків вибирають овочеве блюдо. Ми можемо використовувати це для оцінки ймовірностей на перших двох етапах, як зазначено на деревоподібній діаграмі малюнка 3.2.

Ми вибираємо для нашого зразкового простору набір$\Omega$ всіх можливих шляхів$\omega = \omega_1$$\omega_2$,...,$\omega_6$ через дерево. Як ми повинні призначити наш розподіл ймовірностей? Наприклад, яку ймовірність ми повинні присвоїти клієнту, який вибирає суп, а потім м'ясо? Якщо 8/10 клієнтів вибирають суп, а потім 1/2 з них вибирають м'ясо,$8/10 \cdot 1/2 = 4/10$ частка клієнтів вибирають суп, а потім м'ясо. Це пропонує вибрати наш розподіл ймовірностей для кожного шляху через дерево, щоб бути добутком ймовірностей на кожному з етапів на шляху. Це призводить до розподілу ймовірностей для вибіркових точок,$\omega$ зазначених на малюнку 3.2. (Зауважте, що$m(\omega_1) + \cdots + m(\omega_6) = 1$.) З цього ми бачимо, наприклад, що ймовірність того, що клієнт вибирає м'ясо, є$m(\omega_1) + m(\omega_4) = .46$.

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

Приклад$\PageIndex{2}$

Ми можемо показати, що в Колумбусі, штат Огайо, є щонайменше дві людини, які мають однакові три ініціали. Якщо припустити, що кожна людина має три ініціали, існує 26 можливостей для першого початкового, 26 для другого і 26 для третього. Тому$26^3 = 17,576$ можливі набори ініціалів. Це число менше, ніж кількість людей, які проживають у Колумбусі, штат Огайо; отже, має бути принаймні дві людини з однаковими трьома ініціалами.

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

Приклад$\PageIndex{3}$: Birthday Problem

Скільки людей нам потрібно мати в кімнаті, щоб зробити вигідну ставку (ймовірність успіху більше 1/2), що двоє людей в кімнаті матимуть однаковий день народження?

Рішення

Оскільки існує 365 можливих днів народження, спокусливо здогадатися, що нам знадобиться приблизно 1/2 цього числа, або 183. Ви, безсумнівно, виграєте цю ставку. Насправді кількість, необхідне для вигідної ставки, становить всього 23. Щоб показати це, ми знаходимо ймовірність$p_r$ того, що в кімнаті з$r$ людьми немає дублювання днів народження; у нас буде вигідна ставка, якщо ця ймовірність менше половини.

Проблема дня народження.

Кількість людей	Ймовірність того, що всі дні народження різні
20	.5885616
21	.5563117
22	.5243047
23	.4927028
24	.4616557
25	.4313003

Припустимо, що існує 365 можливих днів народження для кожної людини (ми ігноруємо високосні роки). Замовляйте людей від 1 до$r$. Для вибіркової точки$\omega$ ми вибираємо можливу послідовність$r$ тривалості днів народження, кожен обраний як одну з 365 можливих дат. Існує 365 можливостей для першого елемента послідовності, і для кожного з цих варіантів є 365 для другого, і так далі, що робить$365^r$ можливими послідовності днів народження. Ми повинні знайти кількість цих послідовностей, які не мають дублювання днів народження. Для такої послідовності ми можемо вибрати будь-який з 365 днів для першого елемента, потім будь-який з решти 364 для другого, 363 для третього і так далі, поки не зробимо$r$ вибір. Для вибору$r$ знайдуться$365 - r + 1$ можливості. Отже, загальна кількість послідовностей без дублікатів

$$365 \cdot 364 \cdot 363 \cdot \dots \cdot (365 - r + 1)\ .$$

Таким чином, припускаючи, що кожна послідовність однаково вірогідна,

$$p_r = \frac{365 \cdot 364 \cdot \dots \cdot (365 - r + 1)}{365^r}\ .$$

Позначаємо твір $$(n)(n-1)\cdots (n - r +1)$$ по$(n)_r$ (читаємо «$n$вниз»$r$, або$r$ «$n$нижче»). Таким чином,

$$p_r = \frac{(365)_r}{(365)^r}\ .$$

Програма Birthday проводить цей розрахунок і друкує ймовірності$r = 20$ до 25. Запустивши цю програму, отримуємо результати, наведені в таблиці 3.1.

Як ми стверджували вище, ймовірність відсутності дублювання змінюється від більшої половини до менше половини, оскільки ми переходимо від 22 до 23 осіб. Щоб побачити, наскільки малоймовірно, що ми втратимо нашу ставку для більшої кількості людей, ми знову запустили програму, роздрукувавши значення від$r = 10$ до$r = 100$ з кроком 10. Ми бачимо, що в кімнаті з 40 людей шанси вже сильно сприяють дублюванню, а в кімнаті 100 шанси в переважній більшості на користь дублювання.

Проблема дня народження

Кількість людей	Ймовірність того, що всі дні народження різні
10	.8830518
20	.5885616
30	.2936838
40	.1087682
50	.0296264
60	.0058773
70	.0008404
80	.0000857
90	.00000062
100	.0000003

Ми припустили, що дні народження однаково ймовірно припадуть на будь-який конкретний день. Статистичні дані свідчать про те, що це неправда. Однак інтуїтивно зрозуміло (але нелегко довести), що це робить ще більш імовірним дублювання з групою з 23 осіб. (Див. розділ Вправи,$\PageIndex{19}$ щоб дізнатися, що відбувається на планетах з більшим або менше 365 днів на рік.)

Перестановки

Тепер перейдемо до теми перестановок.

Визначення$PageIndex{1}$: Permutation

$A$Дозволяти бути будь-який кінцевий набір. Перестановка$A$ - це відображення один до одного$A$ на себе.

Щоб вказати певну перестановку, ми перерахуємо елементи$A$ і, під ними, покажемо, куди кожен елемент надсилається відображенням один до одного. Наприклад, якщо$A = \{a,b,c\}$ можлива перестановка$\sigma$ буде

$$\sigma = \pmatrix{ a & b & c \cr b & c & a \cr}.$$

За перестановкою$\sigma$,$a$ відправляється в$b$$c$,$b$ відправляється і$c$ відправляється в$a$. Умова, що відображення буде один до одного означає, що жодні два елементи не$A$ надсилаються, шляхом відображення, в один і той же елемент$A$.

Ми можемо помістити елементи нашого набору в певному порядку і перейменувати їх 1, 2,...,$n$. Потім типову перестановку$A = \{a_1,a_2,a_3,a_4\}$ множини можна записати у вигляді

$$\sigma = \pmatrix{ 1 & 2 & 3 & 4 \cr 2 & 1 & 4 & 3 \cr},$$

вказуючи$a_2$, що$a_1$ пішов$a_2$ до$a_1$,$a_3$ до$a_4$, і$a_4$ до$a_3$.

Якщо ми завжди вибираємо верхній ряд, щоб бути 1 2 3 4, то, щоб прописати перестановку, нам потрібно тільки дати нижній ряд, з розумінням, що це говорить нам, куди йде 1, 2 йде, і так далі, під відображення. Коли це робиться, перестановку часто називають перестановкою$n$ об'єктів 1, 2, 3,...,$n$. Наприклад, всі можливі перестановки або$A = \{1,2,3\}$ перестановки чисел: $$123,\ 132,\ 213,\ 231,\ 312,\ 321\ .$$

Підрахувати кількість можливих перестановок$n$ об'єктів нескладно. За нашим загальним принципом підрахунку існують$n$ способи привласнення першого елемента, для кожного з них у нас є$n - 1$ способи призначити другий об'єкт,$n - 2$ для третього і так далі. Це доводить наступна теорема.

Теорема$PageIndex{1}$

Загальна кількість перестановок множини$A$$n$ елементів задається за$n \cdot (n-1) \cdot (n - 2) \cdot \ldots \cdot 1$.

Іноді корисно розглянути порядок підмножин заданої множини. Це підказує наступне визначення.

$A$Дозволяти бути$n$ -element набір, і нехай$k$ бути ціле число між 0 і$n$. Тоді$k$ -перестановка$A$ - це впорядкований список$A$ підмножини розміру$k$.

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

Теорема$PageIndex{2}$

Загальна кількість$k$ -перестановок множини$A$$n$ елементів задається за допомогою$n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n - k + 1)$.

Факторіали

Число, наведене в$\PageIndex{1}$ теоремі, називається$n$ факторіальним, і позначається символом$n!$. Вираз 0! визначається як 1, щоб зробити певні формули виходять простішими. Перші кілька значень цієї функції наведені в таблиці 3.3. Читач зауважить, що ця функція зростає дуже швидко.

Значення факторіальної функції.

$n$	$n!$
\ (n\) ">0	\ (n! \) ">1
\ (n\) ">1	\ (n! \) ">1
\ (n\) ">2	\ (n! \) ">2
\ (n\) ">3	\ (n! \) ">6
\ (n\) ">4	\ (n! \) ">24
\ (n\) ">5	\ (n! \) ">120
\ (n\) ">6	\ (n! \) ">720
\ (n\) ">7	\ (n! \) ">5040
\ (n\) ">8	\ (n! \) ">40320
\ (n\) ">9	\ (n! \) ">362880
\ (n\) ">10	\ (n! \) ">3628800

Вираз$n!$ увійде до багатьох наших обчислень, і нам потрібно буде мати деяку оцінку його величини, коли$n$ вона велика. Точні розрахунки робити в цьому випадку явно недоцільно. Замість цього ми будемо використовувати результат, який називається формулою Стірлінга. Перш ніж викладати цю формулу, нам потрібно визначення.

Визначення$PageIndex{3}$

$b_n$Дозволяти$a_n$ і бути дві послідовності чисел. Ми говоримо,$a_n$ що асимптотично дорівнює$b_n$, і пишемо$a_n \sim b_n$, якщо

$$\lim_{n \to \infty} \frac{a_n}{b_n} = 1\ .$$

[іспит 3.4] Якщо$a_n = n + \sqrt n$ і$b_n = n$ тоді, так як$a_n/b_n = 1 + 1/\sqrt n$ і це співвідношення прагне до 1 як$n$ прагне до нескінченності, ми маємо$a_n \sim b_n$.

Теорема$\PageIndex{3}$(Stirling's Formula)

$n!$Послідовність асимптотично дорівнює

$$n^ne^{-n}\sqrt{2\pi n}\ .$$ .

Доказ формули Стірлінга можна знайти в більшості аналітичних текстів. Перевіримо це наближення за допомогою комп'ютера. Програма StirlingApximations друкує$n!$, наближення Стірлінга, і, нарешті, співвідношення цих двох чисел. Приклад виведення цієї програми наведено в таблиці 3.4. Зверніть увагу, що в той час як відношення чисел наближається до 1, різниця між точним значенням і наближенням зростає, і дійсно, ця різниця буде прагнути до нескінченності, як$n$ прагне до нескінченності, хоча співвідношення має тенденцію до 1. (Це також було вірно в нашому прикладі$\PageIndex{4}$ де$n + \sqrt n \sim n$, але різниця є$\sqrt n$.)

Таблиця 3.4: Наближення Стірлінга до факторіальної функції.

$n$	$n!$	наближення	Співвідношення
\ (n\) ">1	\ (n! \) ">1	0,922	1.084
\ (n\) ">2	\ (n! \) ">2	1.919	1.042
\ (n\) ">3	\ (n! \) ">6	5.836	1.028
\ (n\) ">4	\ (n! \) ">24	23.506	1.021
\ (n\) ">5	\ (n! \) ">120	118.019	1.016
\ (n\) ">6	\ (n! \) ">720	710.078	1.013
\ (n\) ">7	\ (n! \) ">5040	4980.396	1.011
\ (n\) ">8	\ (n! \) ">40320	39902.395	1.010
\ (n\) ">9	\ (n! \) ">362880	359536.873	1.009
\ (n\) ">10	\ (n! \) ">3628800	35 98696.619	1.008

Генерування випадкових перестановок

Розглянемо тепер питання генерації випадкової перестановки цілих чисел між 1 і$n$. Розглянемо наступний експеримент. Починаємо з колоди$n$ карт, маркованих 1 наскрізь$n$. Вибираємо випадкову карту з колоди, відзначаємо її мітку, і відкладаємо карту в сторону. Повторюємо цей процес до тих пір, поки не будуть обрані всі$n$ карти. Зрозуміло, що кожна перестановка цілих чисел від 1 до$n$ може відбуватися як послідовність міток в цьому експерименті, і що кожна послідовність міток однаково ймовірна. У наших реалізаціях комп'ютерних алгоритмів вищевказана процедура називається Random Permutation.

Фіксовані точки

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

$p_k(n)$Дозволяти ймовірність того, що випадкова перестановка множини$\{1, 2, \ldots, n\}$ має точно$k$ фіксовані точки. Ми спробуємо дізнатися щось про ці ймовірності за допомогою моделювання. Програма FixedPoints використовує процедуру RandomPermutation для генерації випадкових перестановок та підрахунку фіксованих точок. Програма друкує частку разів, що є$k$ фіксовані точки, а також середню кількість фіксованих точок. Результати цієї програми для 500 симуляцій для випадків$n = 10$, 20 і 30 наведені в таблиці 3.5.

Розподіли фіксованих точок.

Кількість фіксованих точок	Частка перестановок
	п = 10	п = 20	п = 30
0	0,362	0,370	0,358
1	0,368	0,396	0,358
2	0,202	0.164	0,192
3	0,052	0,060	0,070
4	0,012	0,008	0,020
5	0,004	0,002	0,002
Середня кількість фіксованих точок	0,996	0,948	1.042

Зверніть увагу на досить дивовижний факт, що наші оцінки ймовірностей, здається, не дуже сильно залежать від кількості елементів у перестановці. Наприклад, ймовірність того, що немає фіксованих точок, коли$n = 10,\ 20,$ або 30 оцінюється в межах від 0,35 до .37. Ми побачимо пізніше (див. Приклад$\PageIndex{12}$, що для$n \geq 10$$p_n(0)$ точних ймовірностей, до шести десяткових знаків точності, дорівнює$1/e \approx .367879$. Таким чином, для всіх практичних цілей не залежить ймовірність того$n = 10$, що випадкова перестановка$\{1, 2, \ldots, n\}$ множини не має фіксованих точок$n$. Ці симуляції також дозволяють припустити, що середня кількість фіксованих точок близька до 1. Можна показати (див. Приклад$\PageIndex{1}$), що середнє значення рівно дорівнює 1 для всіх$n$.

Більш мальовничими варіантами проблеми з фіксованою точкою є: Ви розташували книги на своїй книжковій полиці в алфавітному порядку за автором, і вони випадково повертаються на вашу полицю; яка ймовірність того, що саме$k$ книги потраплять у правильне положення? (Проблема бібліотеки.) У ресторані перевіряються$n$ капелюхи, і вони безнадійно перебираються; яка ймовірність того, що ніхто не отримає власну шапку назад? (Проблема перевірки капелюха.) У історичних зауваженнях в кінці цього розділу ми наведемо один метод для точного вирішення проблеми перевірки капелюхів. Інший метод наведено в прикладі$\PageIndex{13}$

Записи

Ось ще одна цікава проблема ймовірності, яка передбачає перестановки. Оцінки кількості вимірюваного снігу в дюймах в Ганновері, штат Нью-Гемпшир, за десять років з 1974 по 1983 рік наведені в таблиці 3.4.

Снігопад у Ганновері.

Дата	Снігопад в дюймах
1974	75
1975	88
1976	72
1977	110
1978	85
1979	30
1980	55
1981	86
1982	51
1983	64

Припустимо, ми почали вести облік в 1974 році. Тоді наш перший рік снігопад можна вважати рекордним снігопадом, починаючи з цього року. Новий рекорд був встановлений в 1975 році, наступний рекорд був встановлений в 1977 році, а нових рекордів після цього року не було. Так, в цей десятирічний період було встановлено три рекорди: 1974, 1975, і 1977. Питання, яке ми задаємо, полягає в тому, скільки записів ми повинні очікувати, що буде встановлено за такий десятирічний період? Ми можемо підрахувати кількість записів з точки зору перестановки наступним чином: Ми нумеруємо роки від 1 до 10. Фактичні обсяги снігопаду не важливі, але їх відносні розміри є. Таким чином, ми можемо змінити числа, що вимірюють снігопади, на цифри від 1 до 10, замінивши найменше число на 1, наступне найменше на 2 тощо. (Припускаємо, що зв'язків немає.) Для нашого прикладу отримаємо дані, наведені в таблиці 3.7.

5.5 в рік .5 в 1.3 в 2.3 в 3.3 в 4.3 в 5.3 з 6.3 в 7.3 в 8.3 в 9.3 в 10
.5 в рейтингу 6 9 5 10 7 1 3 8 2 4

Це дає нам перестановку чисел від 1 до 10, і з цієї перестановки ми можемо зчитувати записи; вони знаходяться в роках 1, 2 і 4. Таким чином, ми можемо визначити записи для перестановки наступним чином:

$\sigma$Дозволяти бути перестановкою множини$\{1, 2, \ldots, n\}$. Тоді$i$ це запис,$\sigma$ якщо або$i = 1$ або$\sigma(j) < \sigma(i)$ для кожного$j = 1,\ldots,\,i - 1$.

Тепер, якщо ми вважаємо, що всі рейтинги снігопадів за період$n$ -рік однаково вірогідні (і не допускають зв'язків), ми можемо оцінити ймовірність того, що будуть$k$ записи в$n$ роках, а також середню кількість записів шляхом моделювання.

Ми написали програму Records, яка підраховує кількість записів у випадково обраних перестановках. Ми запустили цю програму для випадків$n = 10$, 20, 30. Для$n = 10$ середньої кількості записів 2,968, для 20 - 3,656, а для 30 - 3,960. Зараз ми бачимо, що середні показники збільшуються, але дуже повільно. Пізніше ми побачимо (див. Приклад$\PageIndex{11}$), що середнє число приблизно$\log n$. Так як$\log 10 = 2.3$$\log 20 = 3$, і$\log 30 = 3.4$, це узгоджується з результатами наших симуляцій.

Як зазначалося раніше, ми зможемо отримати формули для точних результатів певних задач вищевказаного типу. Однак лише незначні зміни в проблемі роблять це неможливим. Сила моделювання полягає в тому, що незначні зміни в проблемі не роблять моделювання набагато складніше. (Див. Вправа$\PageIndex{20}$ для цікавого варіанту проблеми перевірки капелюхів.)

Список перестановок

Ще один метод вирішення проблем, які не чутливі до дрібних змін у проблемі, полягає в тому, щоб комп'ютер просто перерахував всі можливі перестановки і підраховував дріб, який має потрібну властивість. Програма AllPermutations виробляє список всіх перестановок$n$. Коли ми намагаємося запустити цю програму, ми стикаємося з обмеженням на використання комп'ютера. Кількість перестановок$n$ збільшується настільки стрімко, що навіть перераховувати всі перестановки 20 об'єктів недоцільно.

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

Наш основний принцип підрахунку говорив, що якщо ви можете зробити одну річ$r$ способами і для кожної з цих іншої речі$s$ способами, то ви можете зробити пару$rs$ способами. Це такий самоочевидний результат, що можна очікувати, що він стався дуже рано в математиці. Н.Л. Біггс припускає, що ми можемо простежити приклад цього принципу наступним чином: По-перше, він пов'язує популярну дитячу риму, що датується принаймні 1730 роком:

Коли я йшов до Сент-Айвз,

Я зустрів чоловіка з сімома дружинами,

У кожної дружини було сім мішків,

У кожному мішку було сім кішок,

У кожного кота було по сім комплектів.

Набори, кішки, мішки і дружини,

Скільки збиралися в Сент-Айвз?

(Вам потрібен наш принцип тільки в тому випадку, якщо ви недостатньо розумні, щоб зрозуміти, що ви повинні відповісти одному, так як тільки оповідач збирається в Сент-Айвз; інші йдуть в іншому напрямку!)

Він також дає проблему, що з'являється на одному з найстаріших збережених математичних рукописів близько 1650 року до н.е., що приблизно перекладається як:

Будинки	7
Кішки	49
Миші	343
Пшениця	2401
Геката	16807
	19607

Було запропоновано наступне тлумачення: є сім будинків, в кожному з яких сім котів; кожна кішка вбиває сім мишей; кожна миша з'їла б сім голів пшениці, кожна з яких виробляла б сім хекат мір зерна. При такому тлумаченні таблиця відповідає на питання про те, скільки заходів хекат врятували дії кішок. Незрозуміло, чому письменник таблиці хотів скласти цифри воєдино. ¹

Одне з найбільш ранніх застосувань факторіалів сталося в доказі Евкліда, що існує нескінченно багато простих чисел. Евклід стверджував, що між ними$n$ має бути просте число:$n!$ і$n! + 1$ не може мати загальних факторів.$n! + 1$ Або$n! + 1$ є простим, або він має належний фактор. В останньому випадку цей фактор не може ділитися$n!$ і, отже, повинен бути між$n$ і$n! + 1$. Якщо цей коефіцієнт не є простим, то він має коефіцієнт, який, за тим же аргументом, повинен бути більше, ніж$n$. Таким чином, ми врешті-решт досягаємо простого більшого$n$, ніж, і це тримається для всіх$n$.

«$n!$" правило щодо кількості перестановок, здається, відбулося спочатку в Індії. Приклади були знайдені ще в 300 році до н.е., і до одинадцятого століття загальна формула, здається, була добре відома в Індії, а потім і в арабських країнах.

Проблема перевірки капелюхів зустрічається в ранній книзі ймовірності, написаної де Монмортом і вперше надрукованої в 1708 році. ² Виявляється у вигляді гри під назвою Treize. У спрощеній версії цієї гри, розглянутої де Монморт, один перевертає карти під номером від 1 до 13, викликаючи 1, 2,..., 13, як карти розглядаються. Де Монморт запитав про ймовірність того, що жодна картка, яка виявилася, не погоджується з номером викликаного.

Ця ймовірність така ж, як і ймовірність того, що випадкова перестановка 13 елементів не має фіксованої точки. Де Монморт вирішив цю задачу використанням рекурсійного відношення наступним чином: нехай$w_n$ буде кількість перестановок$n$ елементів без фіксованої точки (такі перестановки називаються derangements). Потім$w_1 = 0$ і$w_2 = 1$.

Тепер припустимо, що$n \ge 3$ і вибрати розбіжність цілих чисел між 1 і$n$. $k$Дозволяти ціле число в першій позиції в цьому derangement. За визначенням розбіжності ми маємо$k \ne 1$. Є дві можливості інтересу щодо позиції 1 в розряді: або 1 знаходиться в$k$ -й позиції, або в іншому місці. У першому випадку$n-2$ решта цілих чисел можна розташувати таким$w_{n-2}$ чином, не отримуючи ніяких фіксованих точок. У другому випадку розглянемо множину цілих чисел$\{1, 2, \ldots, k-1, k+1, \ldots, n\}$. Цифри в цьому наборі повинні займати позиції$\{2, 3, \ldots, n\}$ так, щоб жодне з чисел, крім 1 в цьому наборі, не було зафіксовано, а також щоб 1 не знаходився в положенні$k$. Кількість способів досягнення такого роду розташування якраз$w_{n-1}$. Так як є$n-1$ можливі значення$k$, ми бачимо, що $$w_n = (n - 1)w_{n - 1} + (n - 1)w_{n -2}$$ для$n \ge 3$. З цього останнього рівняння можна здогадатися, що послідовність$\{w_n\}$ зростає, як послідовність$\{n!\}$.

Насправді, індукцією легко довести, що $$w_n = nw_{n - 1} + (-1)^n\ .$$ Тоді$p_i = w_i/i!$ задовольняє $$p_i - p_{i - 1} = \frac{(-1)^i}{i!}\ .$$ Якщо підсумувати від$i = 2$ до$n$, і використовувати той факт$p_1 = 0$, що, ми отримуємо $$p_n = \frac1{2!} - \frac1{3!} + \cdots + \frac{(-1)^n}{n!}\ .$$ Це узгоджується з першими$n + 1$ умовами розширення$e^x$ для$x = -1$ і, отже, для великих $n$приблизно$e^{-1} \approx .368$. Девід зауважує, що це, можливо, було першим використанням експоненціальної функції за ймовірністю. ³ Ми побачимо ще один спосіб отримати результат де Монморта в наступному розділі, використовуючи метод, відомий як метод включення-виключення.

Нещодавно пов'язана проблема з'явилася в колонці Мерилін вос Савант. ⁴ Чарльз Прайс писав, щоб запитати про свій досвід гри в певну форму пасьянсу, який іноді називають «розчарування пасьянсу». У цій конкретній грі колода карт перетасовується, а потім роздається по одній карті за раз. У міру роздачі карт гравець відраховує від 1 до 13, а потім починає знову з 1. (Таким чином, кожне число зараховується чотири рази.) Якщо число, яке підраховується, збігається з рангом карти, яка розгортається, то гравець програє гру. Прайс виявив, що він рідко вигравав і задавався питанням, як часто він повинен перемагати. Вос Савант зауважив, що очікувана кількість матчів становить 4, тому виграти гру повинно бути важко.

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

Обговорення цієї проблеми можна знайти в Riordan. ⁵ У цій книзі показано, що як$n \rightarrow \infty$, ймовірність відсутності збігів має тенденцію до$1/e^4$.

Оригінальну гру Treize складніше аналізувати, ніж розчарування пасьянсу. У гру Treize грають наступним чином. Одна людина обирається дилером, а інші - гравцями. Кожен гравець, крім дилера, виставляє частку. Дилер перетасовує карти і повертає їх по одному, закликаючи, «Туз, два, три,..., король», так само, як і в розчаруванні пасьянсу. Якщо дилер проходить через 13 карт без матчу, він платить гравцям суму, рівну їх частці, і угода переходить комусь іншому. Якщо є матч дилер збирає ставки гравців; гравці ставлять нові ставки, і дилер продовжує через колоду, закликаючи: «Туз, два, три,...» Якщо у дилера закінчилися карти, він перестановляє і продовжує підрахунок там, де він зупинився. Він триває до тих пір, поки не буде пробіг 13 без матчу, а потім обраний новий дилер.

Питання на даний момент полягає в тому, скільки грошей дилер може розраховувати на виграш від кожного гравця. Де Монморт виявив, що якщо кожен гравець ставить ставку в 1, скажімо, то дилер виграє приблизно 801 від кожного гравця.

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

265160721560102185822 276079 12734 1827846421 20482139144671537196 208993 1523113435417245349128741440299239239251607694 113500080759178185120138 217687653563178 28555 5859367 25463 200947740373955728074593842787649650764965073864965038 2611893881435 1354736631601700494594270178283066011710795363 1427343824779227 098352817532990359885814 13688367655833113244761531072062747416971930180664915269048438391421790695497603628528528521590 140316 20212060159 15491269 208808249133255538826920554388269 2055 27830810368578 188612088758248800680978640438 1185828348775425605550662878927 12304826997601700116239279330829753364219350 5074540269 25683 1938 878213014427051979 188233036929 13358 25922 20117 22071315611 1497510114983 10634072138969878007996472047088253 38752589 22365813230156135230156230156230156 2301562800 562134 290625658974433971 65719454 12290800708628984 13038 13028 18991167357863623756718491353553621974 488902232671011588010162893135 19792943872237033969679706906906906906906999334788024593135 1979 29438 722370333969699 334758024637695 49873661605 18403 1477561560393 3802570707071195964126824550133 19879 74705469 3517809 38 3750593 488886986723648 46950539868628 26099055862710013181 5062113440705698321474022185 15677066720809 458658937845943 2799868706334161812988630493 493 272872548 18458879353024498 003224 2558 64 46741048 14720 934 10806 13506 13506 1350385697 30489712 130639340515 593 373 1591.

Це від 0,803 до 3 знаків після коми. Опис алгоритму, який використовується для пошуку цієї відповіді, можна знайти на його веб-сторінці. ⁶ Обговорення цієї проблеми та інших проблем можна знайти в Doyle et al. ⁷

Проблема дня народження, здається, не має дуже давньої історії. Проблеми такого типу вперше обговорював фон Мізес. ⁸ Це стало популярним у 1950-х роках книгою Феллера. ⁹

Стірлінг представив свою формулу

$$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$$

у своїй праці Метод Диференціаліс опублікований в 1730 році. ¹⁰ Це наближення було використано де Муавре при встановленні своєї знаменитої центральної граничної теореми, яку ми вивчимо в главі 9. Сам де Муавр самостійно встановив це наближення, але не ідентифікуючи константу$\pi$. Встановивши наближення

$$\frac{2B}{\sqrt n}$$

для центрального члена біноміального розподілу, де константа$B$ визначалася нескінченним рядом, де Муавре пише:

... мій гідний і навчений друг, пан Джеймс Стірлінг, який застосував себе після мене до цього запиту, виявив, що Кількість$B$ дійсно позначає квадратний корінь окружності кола, радіус якого є єдність, так що якщо це окружність$c$ називатися Співвідношення середнього члена до суми з усіх Умов будуть виражені$2/\sqrt{nc}\,$... ¹¹

Вправи

$\PageIndex{1}$Чотири людини повинні бути розташовані поспіль, щоб їх сфотографували. Скільки способів це можна зробити?

$\PageIndex{2}$Автомобільний виробник має чотири кольори, доступні для екстер'єрів автомобілів та три для інтер'єрів. Скільки різних колірних поєднань він може виробляти?

$\PageIndex{3}$У цифровому комп'ютері біт є одним з цілих чисел {0,1}, а слово - це будь-який рядок з 32 біт. Скільки різних слів можливо?

$\PageIndex{4}$Яка ймовірність того, що щонайменше 2 президентів США померли в той же день року? Якщо ви ставите, що це сталося, ви б виграли свою ставку?

$\PageIndex{5}$Існує три різні маршрути, що з'єднують місто А з містом Б. Скільки шляхів можна здійснити в обидва кінці від А до Б і назад? Скільки шляхів при бажанні взяти інший маршрут на зворотному шляху?

$\PageIndex{6}$Розставляючи людей навколо круглого столу, ми враховуємо їх місця відносно один одного, а не фактичне положення якоїсь однієї людини. Покажіть, що$n$ людей можна розташувати навколо круглого столу$(n - 1)!$ способами.

$\PageIndex{7}$П'ять чоловік потрапляють на ліфт, який зупиняється на п'яти поверхах. Припускаючи, що кожен має однакову ймовірність піти на який-небудь один поверх, знайдіть ймовірність того, що всі вони зійдуть на різних поверхах.

$\PageIndex{8}$Кінцева множина$\Omega$ має$n$ елементи. Показати, що якщо ми вважаємо порожній набір і$\Omega$ як підмножини, є$2^n$ підмножини$\Omega$.

$\PageIndex{9}$Більш уточнена нерівність для наближення$n!$ дається $$\sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n + 1)} < n! < \sqrt{2\pi n}\left(\frac ne\right)^n e^{1/(12n)}\ .$$ Write a комп'ютерна програма, щоб проілюструвати цю нерівність для$n = 1$ 9.

$\PageIndex{10}$Перетасовується колода звичайних карт і роздається 13 карт. Яка ймовірність того, що остання роздана карта - туз?

$\PageIndex{11}$Є$n$ претенденти на посаду директора з обчислювальної техніки. Заявники проходять співбесіду самостійно кожним членом пошукової комісії з трьох осіб і ранжуються від 1 до$n$. Кандидат буде найнятий, якщо його або вона посідає перше місце принаймні два з трьох інтерв'юерів. Знайдіть ймовірність того, що кандидат буде прийнятий, якщо члени комітету дійсно не мають можливості взагалі судити кандидатів і просто ранжувати кандидатів випадковим чином. Зокрема, порівняйте цю ймовірність для випадку трьох кандидатів і випадку десяти кандидатів.

$\PageIndex{12}$Симфонічний оркестр має в своєму репертуарі 30 симфоній Гайдна, 15 сучасних творів і 9 симфоній Бетховена. Його програма завжди складається з симфонії Гайдна, за якою слідує сучасний твір, а потім симфонія Бетховена.

1. Скільки різних програм він може грати?
2. Скільки різних програм є, якщо три частини можна грати в будь-якому порядку?
3. Скільки різних програм із трьох частин є, якщо можна відтворити більше одного твору з тієї ж категорії, і вони можуть бути відтворені в будь-якому порядку?

$\PageIndex{13}$Певна держава має номерні знаки із зображенням трьох цифр і трьох букв. Скільки різних номерних знаків можливо

1. якщо цифри повинні прийти перед буквами?
2. якщо немає обмежень на те, де з'являються букви і цифри?

$\PageIndex{14}$Дверцята на комп'ютерному центрі має замок, який має п'ять кнопок, пронумерованих від 1 до 5. Комбінація цифр, що відкриває замок, являє собою послідовність з п'яти чисел і скидається щотижня.

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

$\PageIndex{15}$Обчислювальний центр має 3 процесори, які отримують$n$ робочі місця, причому завдання призначаються процесорам чисто навмання, так що всі$3^n$ можливі призначення однаково вірогідні. Знайдіть ймовірність того, що точно один процесор не має робочих місць.

$\PageIndex{16}$Доведіть, що принаймні дві людини в Атланті, штат Джорджія, мають однакові ініціали, припускаючи, що ніхто не має більше чотирьох ініціалів.

$\PageIndex{17}$Знайдіть формулу ймовірності того, що серед безлічі$n$ людей принаймні два мають свої дні народження в одному місяці року (якщо припустити, що місяці однаково ймовірні для днів народження).

$\PageIndex{18}$Розглянемо проблему знаходження ймовірності не одного збігу днів народження в групі$n$ людей. До них відносяться, наприклад, три людини з однаковим днем народження, або дві пари людей з однаковим днем народження, або більші збіги. Покажіть, як можна обчислити цю ймовірність, і написати комп'ютерну програму для проведення цього обчислення. Використовуйте свою програму, щоб знайти найменшу кількість людей, для яких було б вигідною ставкою, що було б не один збіг днів народження.

$\PageIndex{19}$Припустимо, що на планеті Зорг рік має$n$ дні, і що форми життя там однаково ймовірно вилупилися в будь-який день року. Ми хотіли б оцінити$d$, яка мінімальна кількість життєвих форм, необхідних для того, щоб ймовірність щонайменше двох розділити день народження перевищує 1/2.

1. На прикладі було показано$\PageIndex{3}$, що в сукупності$d$ життєвих форм ймовірність того, що ніякі дві життєві форми не поділяють день народження, становить $$\frac{(n)_d}{n^d} ,$$
2. де$(n)_d = (n)(n-1)\cdots (n-d+1)$. Таким чином, ми хотіли б встановити це рівне 1/2 і вирішити для$d$.
3. Використовуючи формулу Стірлінга, покажіть, що\[
   ParseError: EOF expected (click for details)

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

   \sim \biggl(1 + {d\over{n-d}}\biggr)^{n-d + 1/2} e^{-d}\ .\]
4. Тепер беремо логарифм правого виразу, і використовуємо той факт, що для малих значень$x$, ми маємо $$\log(1+x) \sim x - {{x^2}\over 2}\ .$$ (Ми неявно використовуємо той факт, що$d$ має менший порядок, ніж$n$. Ми також будемо використовувати цей факт частково (d).)
5. Встановіть вираз, знайдене в частині (c) рівне$-\log(2)$, і вирішіть для$d$ як функцію$n$, тим самим показуючи, що $$d \sim \sqrt{2(\log 2)\,n}\ .$$ : Якщо використані всі три доведені у виразі, знайдені в частині (b), один отримує кубічне рівняння в$d$. Якщо викинути найменший з трьох членів, то виходить квадратне рівняння в$d$.
6. Використовуйте комп'ютер для обчислення точних значень$d$ для різних значень$n$. Порівняйте ці значення з приблизними значеннями, отриманими за допомогою відповіді на частину d).

i (\ pageIndex {20}\) На математичній конференції десять учасників випадково сидять за круглим столом для прийому їжі. Використовуючи моделювання, оцініть ймовірність того, що жоден двоє людей не сидять поруч один з одним і за обідом, і за вечерею. Чи можете ви зробити розумну здогадку для випадку$n$ учасників, коли$n$ велика?

$\PageIndex{21}$Змініть програму AllPermutations для підрахунку кількості перестановок$n$ об'єктів, які мають точно$j$ фіксовані точки для$j = 0$, 1, 2,...,$n$. Запустіть програму$n = 2$ до 6. Зробіть гіпотезу для зв'язку між числом, яке має 0 фіксованих точок, і числом, яке має рівно 1 фіксовану точку. Доказ правильної здогадки можна знайти в Wilf. ¹²

$\PageIndex{22}$Містер Вімплі Дімпл, один з найпрестижніших виробників годинників Лондона, прийшов до Шерлока Холмса в паніці, виявивши, що хтось виробляє та продає сирі підробки його найбільш продаваних годинників. 16 підробок досі виявлені ведмеді штамповані цифри, всі вони падають між 1 і 56, і Dimple прагне знати ступінь роботи фальсифікатора. Усі присутні погоджуються з тим, що здається розумним припустити, що підробки, вироблені до цього часу, несуть послідовні цифри від 1 до загальної кількості.

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

«Матеріал, нісенітниця, і турбувати ваші фантазії принципи, Ватсон», - зустрічає Холмс. «Будь-хто може побачити, що, звичайно, має бути досить багато годин 56 - чому шанси на те, що ми виявили саме годинник з найвищим номером, смішно незначні. Набагато краще здогадатися було б 56».

1. Покажіть, що Ватсон правильний, що принцип максимальної правдоподібності дає 56.
2. Напишіть комп'ютерну програму для порівняння стратегій вгадування Холмса та Уотсона наступним чином: виправте загальну суму$N$ та виберіть 16 цілих чисел випадковим чином між 1 та$N$. Давайте$m$ позначимо найбільший з них. Тоді здогадка Уотсона для$N$ є$m$, тоді як Холмс є$2m$. Подивіться, до якого з них ближче$N$. Повторіть цей експеримент (з$N$ ще фіксованим) сто і більше разів, і визначте частку разів, що кожен наближається. Чия, здається, краща стратегія?

$\PageIndex{23}$Барбара Сміт опитує кандидатів, щоб бути її секретарем. Під час співбесіди з кандидатами вона може визначити відносний ранг кандидатів, але не справжній ранг. Таким чином, якщо кандидатів шість, і їх справжній ранг - 6, 1, 4, 2, 3, 5, (де 1 найкращий), то після того, як вона співбесідила з першими трьома кандидатами, вона ранжирувала б їх 3, 1, 2. Коли вона співбесідає з кожним кандидатом, вона повинна або прийняти, або відхилити кандидата. Якщо вона не прийме кандидата після співбесіди, кандидат їй втрачається. Вона хоче визначитися зі стратегією прийняття рішення про те, коли зупинитися і прийняти кандидата, що дозволить максимізувати ймовірність отримання найкращого кандидата. Припустимо, що є$n$ кандидати, і вони прибувають у випадковому порядку рангу.

1. Яка ймовірність того, що Барбара отримає найкращого кандидата, якщо співбесіда з усіма кандидатами? Що це, якщо вона вибирає першого кандидата?
2. Припустимо, що Барбара вирішує взяти інтерв'ю у першій половині кандидатів, а потім продовжувати співбесіду, поки не отримає кандидата краще, ніж будь-який кандидат, який бачив досі. Покажіть, що вона має більше 25 відсотків шансів закінчити з найкращим кандидатом.

$\PageIndex{24}$Для завдання, описаного у Вправі 23, можна показати ¹³, що найкраща стратегія полягає в тому, щоб передати перших$k - 1$ кандидатів, де$k$ найменше ціле число, для якого $$\frac 1k + \frac 1{k + 1} + \cdots + \frac 1{n - 1} \leq 1\ .$$ Використовуючи цю стратегію, ймовірність отримання найкращого кандидата приблизно$1/e = .368$. Напишіть програму для імітації інтерв'ю Барбари Сміт, якщо вона використовує цю оптимальну стратегію$n = 10$, використовуючи, і подивіться, чи зможете ви переконатися, що ймовірність успіху приблизно$1/e$.