Как в учебнике
Для целых $0\le k\le n$ биномиальный коэффициент равен $\binom nk=n!/[k!(n-k)!]$. Он считает способы выбрать $k$ объектов из $n$ различных объектов без учёта порядка. Каждый объект выбирают не более одного раза.
Сначала упорядоченный выбор даёт $n!/(n-k)!$ вариантов. Каждый набор из $k$ объектов представлен $k!$ перестановками. Деление на $k!$ убирает повторный подсчёт. При $k=0$ или $k=n$ получается 1: выбрать ничего или всё можно единственным способом.
Симметрия $\binom nk=\binom n{n-k}$ следует из соответствия между выбранным набором и набором оставшихся объектов. Каждому выбору $k$ объектов отвечает ровно один остаток из $n-k$ объектов, и наоборот. Это не разрешает выбирать один объект несколько раз: такая задача меняет множество допустимых наборов. Формула также не различает роли внутри выбранной группы, поскольку перестановки уже устранены делением.
Определения и дальнейшее чтение: Mathematics for Computer Science.
На пальцах
Биномиальный коэффициент считает наборы заданного размера из разных объектов, когда порядок выбора не важен. При выборе двух участников из четырёх Аня–Боря и Боря–Аня обозначают одну пару, поэтому перестановки выбранных людей исключаются из подсчёта. При назначении капитана и заместителя распределение ролей уже создаёт разные результаты, и прежняя модель выбора не подходит. Формула считает состав, а не читает положение о конкурсе и не оценивает красоту списка фамилий.
Пример
Для учебных карточек A, B, C, D перечислены пары. Сначала порядок создаёт 12 вариантов, затем каждая пара объединяется с перестановкой тех же карточек. Остаются шесть наборов.
Биномиальный коэффициент: выбор без порядка
Упорядоченный выбор
Четыре выбора первого и три выбора второго дают 12.
Шаг 1 из 3: Упорядоченный выбор
Все шаги текстом
Упорядоченный выбор
Четыре выбора первого и три выбора второго дают 12.
- Состояние
- ABтекущийACтекущийADтекущийBAтекущийBCтекущийBDтекущийCAтекущийCBтекущийCDтекущийDAтекущийDBтекущийDCтекущий
Повторный подсчёт
AB и BA обозначают один набор.
- Состояние
- AB = BAтекущийAC = CAтекущийAD = DAтекущийBC = CBтекущийBD = DBтекущийCD = DCтекущий
Шесть наборов
После деления на два каждый набор посчитан один раз.
- Состояние
- ABтекущийACтекущийADтекущийBCтекущийBDтекущийCDтекущий
Шесть наборов можно проверить списком AB, AC, AD, BC, BD, CD. Каждый появляется среди двенадцати упорядоченных пар ровно два раза, поэтому деление одинаково для всех наборов. Пара AA не возникает: после первого выбора карточка уже недоступна. Если включить её в подсчёт, получится другая задача, и деление прежнего количества перестановок больше не исправит исходный список.
Дальше: Факториал.