Словник / Комбінаторика
Візьміть звичайну колоду з 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) — тонша поправка, і π у ній береться з того самого інтеграла, що дає площу під кривою Гаусса нормального розподілу.
Число посередині: якщо всіх вишикувати за зростанням, половина буде нижче, половина вище.
До бару заходить мільйонер, і середній дохід відвідувачів злітає, а медіана ледь ворухнеться.
Сума всіх значень, поділена на їхню кількість: скільки дісталося б кожному, якби поділити порівну.
Майже кожна людина має більше ніг, ніж у середньому: середнє трохи менше за дві.
Середній результат, якого можна чекати, якщо повторювати те саме дуже багато разів.
У грального кубика сподівання 3,5, хоча такої грані немає.
Число від −1 до +1, що показує, наскільки дві величини рухаються разом.
Улітку ростуть і продаж морозива, і кількість утоплень. Морозиво тут ні до чого: обох розганяє спека.
Міра розкиду: наскільки значення в середньому відходять від середнього. Стандартне відхилення — корінь з дисперсії, у тих самих одиницях.
Два міста з однаковою середньою температурою: в одному весь рік близько +15, в іншому то −20, то +50.
Розподіл у формі дзвона: більшість значень біля середнього, а що далі від нього, то рідше.
Кожна кулька на дошці Гальтона падає навмання, а тисячі кульок щоразу складаються в той самий дзвін.
Що більше повторень, то ближче частка результату до його справжньої ймовірності.
Частка орлів підповзає до 50%, а різниця між орлами й решками в штуках зазвичай росте.
Шанс події за умови, що вже відомо щось інше.
Майже всі баскетболісти НБА високі, але майже всі високі люди не баскетболісти.
Події незалежні, якщо знання про одну не змінює шансів іншої.
Після п'яти орлів поспіль решка не стає ймовірнішою: монета нічого не пам'ятає.
Скільки разів треба помножити основу саму на себе, щоб отримати число: log₂ 8 = 3, бо 2 · 2 · 2 = 8.
Аркуш паперу, складений навпіл 42 рази, був би товщим за відстань до Місяця.
Вибірка, у яку одні потрапляють частіше за інших, тож вона погано описує всіх.
1936 року журнал опитав мільйони американців і все одно помилився з переможцем виборів.
Як часто сам лише випадок дав би розрив щонайменше такий, як у вас, якби різниці насправді не було.
Коли ефекту немає зовсім, p < 0,05 випадає так само часто, як p між 0,50 і 0,55.
Діапазон навколо виміряного числа, побудований методом, що накриває справжнє значення в обраній частці вибірок, наприклад у 95%.
Із двадцяти чесних 95% інтервалів у середньому один промахується, і жоден не знає, чи це він.
Імовірність, що тест помітить справжній ефект заданого розміру. Потужність 80% означає: один робочий ефект із п'яти тест пропустить.
Слабкий A/B-тест, який таки знайшов ефект, майже завжди його перебільшує: справжні +10% на дашборді стають +24%.
Наскільки зазвичай промахується середнє чи частка, пораховані з вибірки: σ, поділене на корінь з розміру вибірки.
Щоб удвічі зменшити похибку, треба вчетверо більше даних.
Сума 1 + ½ + ⅓ + ¼ + …: вона росте без меж, але неймовірно повільно.
Однакові книжки можна скласти так, що верхня нависатиме над краєм столу як завгодно далеко.
Правило, як змінювати впевненість, коли з'являються нові докази: апріорні шанси × сила доказу.
Два слабкі докази разом бувають сильними, а один яскравий нічого не важить, якщо твердження було малоймовірним.
Зростання, за якого величина щоразу множиться на те саме число, тож подвоюється через рівні проміжки часу.
Одне зернятко на першій клітинці шахівниці й подвоєння на кожній наступній: на останній клітинці стільки рису, скільки світ вирощує понад 300 років.
Рух, у якому кожен наступний крок робиться навмання: вперед чи назад, ліворуч чи праворуч.
П'яний завжди дійде додому, а птах, що літає навмання, може не повернутися ніколи.
Потік незалежних випадкових подій зі сталою середньою частотою: дзвінки, клацання лічильника, краплі дощу.
У 1944 році лондонцям здавалося, що німецькі літаючі бомби влучають прицільно, а це була звичайна випадкова купчастість.