Комбинаторика: искусство подсчёта

Почему в задаче о рукопожатиях 30 гостей дают $\binom{30}{2}=435$ рукопожатий, а не $30\times 30 = 900$?

$30\times 30$ считает упорядоченные пары вместе с самопожатиями. Реальный счёт: $\binom{30}{2} = \frac{30\cdot 29}{2} = 435$ - выбираем 2 человек из 30 без порядка.

Утренний образ

Выбираем одежду

5 рубашек **И** 3 пары брюк. Сколько образов? $5 \times 3 = 15$ образов Почему умножение? Для каждой рубашки подходят все 3 пары брюк - выборы независимы. Добавить 4 пары обуви: $5 \times 3 \times 4 = 60$ образов. То же правило стоит за числом конфигураций нейросети: если слой 1 имеет $m$ возможных состояний, слой 2 - $n$, сеть из двух слоёв имеет $m \times n$ конфигураций.

Как добраться до офиса

Альтернативы

До офиса ходят 3 автобуса **ИЛИ** 2 троллейбуса. $3 + 2 = 5$ способов **Почему сложение?** Потому что это *альтернативы* - едешь или на одном, или на другом, не на обоих сразу.

В меню 4 салата, 5 основных блюд и 3 десерта. Сколько способов заказать обед из салата, основного И десерта?

Ключевое слово - "И". Нужно выбрать И салат, И основное, И десерт. Каждый выбор независим → умножаем.

Фотография друзей

4 человека в ряд

Аня, Боря, Вася, Галя встают в ряд для фото. $P_4 = 4! = 4 \times 3 \times 2 \times 1 = 24$ способа Логика: - Первым может встать любой из 4 - Вторым - любой из оставшихся 3 - Третьим - любой из 2 - Последний - единственный оставшийся

Анаграммы слова "АББА"

Сколько разных перестановок?

Слово "АББА" - 4 буквы: А(2 раза), Б(2 раза) Если бы все были разные: $4! = 24$ Но А можно переставить между собой $2!$ способами, и Б тоже $2!$ - это не меняет слово! $P = \frac{4!}{2! \cdot 2!} = \frac{24}{4} = 6$ Проверка: ААББ, АБАБ, АББА, БААБ, БАБА, ББАА - ровно 6!

Spotify хочет перемешать плейлист из 10 треков. Сколько существует порядков?

Это классическая перестановка: расставить все 10 треков в определённом порядке. Первый трек - 10 вариантов, второй - 9, и т.д. Итого $10!$

Призовые места

Забег 10 спортсменов

Сколько способов распределить золото, серебро, бронзу среди 10 спортсменов? $A_{10}^3 = 10 \times 9 \times 8 = 720$ способов **Порядок важен!** "Иванов-золото, Петров-серебро" ≠ "Петров-золото, Иванов-серебро"

4-значный PIN-код

Сколько комбинаций?

Цифры: 0-9 (n = 10), длина: 4 (k = 4) $\bar{A}_{10}^4 = 10^4 = 10\,000$ кодов От 0000 до 9999 - ровно 10 000 вариантов. GPU перебирает их меньше чем за миллисекунду. Именно поэтому PIN из 4 цифр - лишь замедление, не защита. 8 символов из 62 - $62^8 \approx 218$ триллионов: уже другой масштаб.

"Размещение и перестановка - одно и то же"

Перестановка - это размещение ВСЕХ элементов ($k = n$)

Перестановка $P_n = n!$ - частный случай размещения при $k = n$: $A_n^n = n!/(n-n)! = n!/0! = n!$. При $k < n$ - это уже размещение. Различие важно: beam search выбирает $k$ токенов из словаря размером $n$ с учётом порядка - это $A_n^k$, не $n!$.

Пароль из 8 символов (a-z, A-Z, 0-9 = 62 символа), повторения разрешены. Сколько вариантов?

Размещение с повторениями: на каждую из 8 позиций - 62 варианта. Итого $62^8$ ≈ 218 триллионов. Поэтому 8-символьный пароль считается надёжным!

Лотерея "6 из 49"

Шанс сорвать джекпот

Нужно угадать 6 чисел из 49. Порядок не важен - только какие выпали. $C_{49}^6 = \frac{49!}{6! \cdot 43!} = \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{720} = 13\,983\,816$ **Вероятность джекпота:** $\frac{1}{13\,983\,816} \approx 0.000007\%$ Чтобы гарантировать выигрыш, нужно купить 14 миллионов билетов!

Команда для проекта

Выбираем 3 из 10

Сколько способов выбрать команду из 3 человек из группы в 10? $C_{10}^3 = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{6} = 120$ способов В команде нет ролей - {Аня, Боря, Вася} = {Вася, Аня, Боря}.

"Если не знаю, использую сочетания - формула проще"

Сочетания или размещения - зависит ТОЛЬКО от того, важен ли порядок

Один вопрос расставляет всё по местам: если переставить выбранные элементы местами - изменится ли результат? ДА (медали, должности, токены в тексте) - размещение. НЕТ (лотерея, команда без ролей, набор признаков) - сочетание. Наивный Байес предполагает, что слова в письме - это именно сочетание: порядок не важен, важно только какие слова есть.

Выбираем президента, вице-президента и казначея из 10 человек. Что использовать?

Порядок ВАЖЕН! Президент ≠ казначей. Одни и те же 3 человека могут занять должности по-разному. Поэтому размещение, а не сочетание.

Вернёмся к рукопожатиям: 30 гостей, каждый пожал руку каждому. Сколько рукопожатий?

Рукопожатие - это пара людей. Порядок НЕ важен: "Аня-Боря" = "Боря-Аня". Поэтому сочетание! $C_{30}^2 = \frac{30 \times 29}{2} = 435$. Ошибка "$30 \times 30$" считает каждое рукопожатие дважды + рукопожатия с самим собой.

Покер: вероятность пары

Одна из самых частых комбинаций

Пара - ровно две карты одного номинала (два туза, две семёрки и т.д.) **Благоприятных исходов:** 1. Выбираем номинал пары: $C_{13}^1 = 13$ 2. Выбираем 2 масти из 4: $C_4^2 = 6$ 3. Выбираем 3 номинала для остальных: $C_{12}^3 = 220$ 4. Для каждого - 1 масть из 4: $4^3 = 64$ Итого: $13 \times 6 \times 220 \times 64 = 1\,098\,240$ **Всего 5-карточных рук:** $C_{52}^5 = 2\,598\,960$ $P(\text{пара}) = \frac{1\,098\,240}{2\,598\,960} \approx 42.3\%$ Пара - самая частая ненулевая комбинация!

Считаем вероятность двух тузов в случайной 5-карточной руке. Какая часть формулы относится к числителю $|A|$?

Числитель $|A|$ перечисляет благоприятные исходы: фиксируем номинал пары, выбираем 2 масти из 4, затем добираем 3 непарных номинала и для каждого по 1 масти. $C_{52}^5$ - это знаменатель $|\Omega|$.

Сколько способов выбрать старосту и заместителя из группы 25 человек?

$A_{25}^2 = 25 \times 24 = 600$ способов

В урне 7 белых и 5 чёрных шаров. Вынимают 3 шара одновременно. Какова вероятность, что все три белые?

Благоприятных (3 белых из 7): $C_7^3 = 35$ Всего (3 любых из 12): $C_{12}^3 = 220$ $P = \frac{35}{220} = \frac{7}{44} \approx 15.9\%$

Автомобильный номер: 3 буквы (из 12 возможных) + 3 цифры. Буквы и цифры могут повторяться. Сколько номеров?

Букв: $12^3 = 1728$ вариантов Цифр: $10^3 = 1000$ вариантов Всего: $1728 \times 1000 = 1\,728\,000$ номеров

Сколько способов расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

Одна ладья на каждой горизонтали, одна на каждой вертикали. Первая ладья: 8 вертикалей Вторая: 7 (одна занята) Третья: 6 ...и так далее $8! = 40\,320$ способов *Это классическая задача, эквивалентная перестановкам чисел 1-8!*

В лотерее нужно угадать 6 номеров из 49. Какова вероятность сорвать джекпот, угадав все 6?

Порядок номеров не важен, повторений нет - значит сочетания. Благоприятный исход один, всего исходов $C_{49}^6 = 13\,983\,816$. Размещения завысят знаменатель в $6!$ раз, а $49^6$ ошибочно допускает повторения.