Словник / Комбінаторика
Візьміть звичайну колоду з 52 карт і добре її перетасуйте. Колодами грають сотні років, мільйони людей щодня, тож здається, що всі порядки давно перебрали. Насправді ваш порядок майже напевно новий: його ще ніхто й ніколи не тримав у руках. Комбінаторика — це вміння рахувати, скількома способами можна щось розкласти чи вибрати, не перебираючи всі способи по одному.
Шар «На пальцях» приховано на всіх задачах.
Почніть з маленької колоди й додавайте карти повзунком. Під картами — скільки існує різних порядків, і скільки часу пішло б, щоб перебрати їх усі, викладаючи по одному порядку щосекунди. Скільки карт треба, щоб на це не вистачило віку Всесвіту?
Скільки карт треба, щоб перебирати порядки довше, ніж:
Для повної колоди порядків приблизно 8 · 1067: вісімка і ще 67 цифр. Уявіть, що всі 8 мільярдів людей тасують колоду щосекунди, і почали ще у Великому вибуху, 13,8 мільярда років тому. Разом вийде близько 3,5 · 1027 перетасовок. Це лише частка 4 · 10−41 від усіх можливих порядків, тобто нічого. Для порівняння: атомів у всій Землі за оцінками фізиків близько 1050, а порядків колоди ще в сотні мільйонів мільярдів разів більше.
Секрет у множенні. Кожна нова карта не додає порядків, а множить їх: її можна вставити в будь-яке місце вже наявного ряду. Сьома карта множить на 7, двадцята — на 20, п'ятдесят друга — на 52.
Шар «Строго» приховано на всіх задачах.
Перестановка — це один зі способів вишикувати n різних предметів у ряд. На перше місце можна поставити будь-який з n, на друге — будь-який з решти n − 1, і так далі до останнього. Число способів позначають n! і читають «n факторіал».
n! = n · (n − 1) · … · 2 · 1 · 3! = 3 · 2 · 1 = 6 · 4! = 24 · 10! = 3 628 800
Часто порядок не важить: важить лише, які саме предмети вибрано. Скільки існує способів вибрати k предметів з n, позначають C(n, k) і читають «сполучення з n по k» (в англійській — «n choose k»).
Спершу рахуємо так, ніби порядок важить: першу кульку можна вибрати 49 способами, другу 48, і так до шостої.
49 · 48 · 47 · 46 · 45 · 44 = 10 068 347 520 упорядкованих виборів
Але кожен квиток — це набір з шести чисел, а одні й ті самі шість чисел можна витягнути в 6! = 720 різних порядках. Тож ділимо:
C(49, 6) = 10 068 347 520 / 720 = 13 983 816 різних квитків
Шанс угадати всі шість одним квитком — один на майже 14 мільйонів.
Усі C(n, k) зручно скласти в трикутник: у рядку n стоять C(n, 0), C(n, 1), … C(n, n). Краї завжди одиниці, а кожне число всередині дорівнює сумі двох над ним. Натисніть на будь-яке число.
–
Шар «Глибше» приховано на всіх задачах.
Упорядкованих виборів k предметів з n стільки: n · (n − 1) · … · (n − k + 1). Цей добуток — це n!, у якому відкинули хвіст (n − k)!. Кожен невпорядкований набір з k предметів потрапив сюди рівно k! разів, по разу на кожне його впорядкування. Тож ділимо ще на k!:
n · (n − 1) · … · (n − k + 1) = n! / (n − k)! ⇒ C(n, k) = n! / (k! · (n − k)!)
Звідси одразу видно симетрію C(n, k) = C(n, n − k): вибрати 6 кульок з 49 — те саме, що вибрати 43, які не потрапили в квиток. Тому трикутник Паскаля симетричний.
C(n, k) = C(n − 1, k − 1) + C(n − 1, k)
Позначте один предмет з n, скажімо туза пік. Усі набори з k предметів діляться на дві купки, що не перетинаються. Або туз у наборі: тоді решту k − 1 предметів вибираємо з n − 1, це C(n − 1, k − 1) способів. Або туза в наборі немає: тоді всі k вибираємо з n − 1, це C(n − 1, k). Разом — усі набори, кожен рівно один раз.
–
Те саме міркування пояснює, чому сума рядка n дорівнює 2n: кожен предмет або беруть, або ні, тож усіх наборів будь-якого розміру 2 · 2 · … · 2.
n! ≈ √(2πn) · (n / e)n
Множити 52 числа довго, а Джеймс Стірлінг ще в 1730 році знайшов короткий шлях. Для двадцяти формула помиляється менш ніж на пів відсотка, і що більше n, то точніше: відносна похибка близько 1 / (12n). Порівняйте з точним значенням.
Звідки тут π і e? Логарифм факторіала — це сума ln 1 + ln 2 + … + ln n, а сума майже дорівнює площі під кривою ln x, тобто приблизно n ln n − n. Звідси множник (n / e)n. Корінь √(2πn) — тонша поправка, і π у ній береться з того самого інтеграла, що дає площу під кривою Гаусса нормального розподілу.
Шанс події за умови, що вже відомо щось інше.
Майже всі баскетболісти НБА високі, але майже всі високі люди не баскетболісти.
Події незалежні, якщо знання про одну не змінює шансів іншої.
Після п'яти орлів поспіль решка не стає ймовірнішою: монета нічого не пам'ятає.
Правило, як змінювати впевненість, коли з'являються нові докази: апріорні шанси × сила доказу.
Два слабкі докази разом бувають сильними, а один яскравий нічого не важить, якщо твердження було малоймовірним.
Скільки успіхів буде в n незалежних спробах, якщо в кожній шанс той самий p.
Підкиньте монетку 100 разів: рівно 50 орлів — найімовірніший результат, але випадає він лише в 8 випадках зі 100.
Скільки відповідей «так чи ні» (бітів) у середньому треба, щоб дізнатися результат: що менш передбачуваний результат, то більша ентропія.
Монета, що падає гербом у 99% випадків, теж може впасти будь-яким боком, але одне її підкидання несе лише 0,08 біта: у 12 разів менше, ніж чесна.