Подсчёт без полного перечисления
Комбинаторика отвечает на вопрос «сколько?», когда перечислить каждое расположение невозможно. В вводном счёте доминируют три классических вопроса: перестановки (важен порядок), сочетания (порядок не важен) и размещения / частичные перестановки (порядок важен, но заполняются только k из n позиций). У каждого вопроса есть вариант с повторениями и без повторений.
Конкретная отправная точка — сочетания без повторений, биномиальный коэффициент «n по k», от которого можно перейти к упорядоченным вариантам или вариантам с повторениями в зависимости от задачи.
Руководство по выбору
Задавайте вопросы по порядку:
- Важен ли порядок? Если да → перестановки / размещения. Если нет → сочетания.
- Может ли один и тот же элемент встретиться более одного раза? Если да → формулы «с повторениями». Если нет → «без повторений».
- Вы упорядочиваете все n элементов или только k из них? Полные перестановки используют n!; частичный выбор — падающие факториалы или n^k.
Неверное понимание любой из этих трёх осей — обычный источник ошибок «в целое число раз» в домашних заданиях и на собеседованиях.
Семейство калькуляторов
- Перестановки без повторений — n! упорядоченных расстановок n различных элементов.
- Перестановки с повторениями — перестановки мультимножеств n! / (r₁! r₂! …), когда есть одинаковые копии.
- Сочетания без повторений — C(n, k) = n! / (k! (n − k)!) неупорядоченные k-подмножества.
- Сочетания с повторениями — C(n + k − 1, k) мультимножества размера k из n типов.
- Размещения без повторений — P(n, k) = n! / (n − k)! упорядоченные k-кортежи без повторного использования.
- Размещения с повторениями — n^k упорядоченные k-кортежи с разрешённым повторным использованием.
Входные данные — неотрицательные целые числа с обычными ограничениями (k ≤ n, когда повторения запрещены, и т. д.). Переполнение факториалов проявляется как ошибка вычисления, а не как тихая бесконечность.
Факториалы как общий механизм
Формулы без повторений опираются на n! — произведение 1 × 2 × … × n, при этом 0! = 1 по соглашению. Сочетания делят внутренний порядок каждого подмножества (k!) и иногда неиспользованный «хвост» ((n − k)!). Частичные перестановки сохраняют порядок, поэтому делят только на (n − k)!.
Сочетания с повторениями используют тождество «stars and bars» C(n + k − 1, k). Размещения с повторениями ещё проще: каждая из k позиций независимо выбирает один из n символов → n^k.
Краткие примеры
Колода из 52, рука из 5 (порядок не важен, без возврата): C(52, 5).
Забег с 8 разными бегунами, золото/серебро/бронза: P(8, 3) = 8 × 7 × 6.
PIN из 4 цифр, цифры могут повторяться: 10^4 = 10000.
Расстановки букв слова «BOOK»: 4! / 2! из-за двух O — перестановка мультимножества.
Купить 3 шарика из 5 вкусов, повторения разрешены, порядок не важен: C(5 + 3 − 1, 3).
Умение сопоставить текстовую задачу с нужным калькулятором — главное; арифметика вторична.
Соотношения, предотвращающие ошибки
- P(n, k) = C(n, k) × k! — сначала выбрать множество, затем упорядочить.
- n! = P(n, n) — полные перестановки — это частичные перестановки при k = n.
- C(n, k) = C(n, n − k) — симметрия биномиальных коэффициентов.
- Запрет повторений, когда задача их допускает, занижает результат; разрешение, когда запрещены, завышает.
Где встречаются эти подсчёты
- Знаменатели вероятностей (честные игры, выборки)
- Наброски стойкости паролей и идентификаторов (с ясными оговорками о модели угроз)
- Анализ алгоритмов (пространства поиска, перечисление состояний)
- Планирование экспериментов (комбинации обработок)
- Спортивные «способы финишировать» и подобные головоломки с ранжированием — как математика, а не совет по ставкам
Большое n растёт быстрее интуиции. C(60, 6) уже миллионы; факториалы за пределами скромного n переполняют числа с фиксированной точностью — отсюда специализированные хелперы и библиотеки больших целых в промышленных системах.
Последовательность обучения
- Считать перестановки малого n перечислением, затем ввести n!.
- Ввести P(n, k) на примерах с пьедесталом.
- Показать C(n, k), вычитая порядок.
- Добавить повторения: сначала n^k (независимые позиции), затем stars and bars.
- Только потом — перестановки мультимножеств с повторяющимися буквами.
Переход сразу к шести похожим формулам без руководства по выбору приводит к механической подстановке без понимания.
Замечания по реализации
Вычисление C(n, k) через три полных факториала просто, но быстро переполняется. Мультипликативные алгоритмы уменьшают промежуточные значения. Хелперы этого хаба используют деление факториалов с проверками конечности, подходящими для интерактивного обучения — не для криптографических масштабов n. Отклонять нецелые числа и невозможные пары (n, k) со стабильными кодами ошибок.
Частые ошибки
- Считать «комитет из 5» перестановкой
- Использовать n^k для выборок без возврата, когда порядок не важен
- Забывать делить на факториалы одинаковых букв в задачах на слова
- Путать сочетания с повторениями и без при покупке «до k товаров»
Итог
Этот хаб объединяет шесть элементарных инструментов подсчёта: полные и мультимножественные перестановки, сочетания с повторениями и без, а также частичные размещения с повторениями и без. Определите, важны ли порядок и повторное использование, выберите подходящую формулу и проверьте на маленьком перечислении. Калькуляторы автоматизируют арифметику, чтобы вы могли сосредоточиться на правильной постановке задачи.