Сколько подмножеств размера k из n элементов
Порядок внутри набора не нумеруют: {1,2} и {2,1} — одно сочетание. Раздел: комбинаторика.
Контроль: C(5,2) = 10. C(5,3) = 10. C(10,0) = 1. C(6,6) = 1.
n и k целые 0…20, k ≤ n. Родитель математика.
C(n, k) = n! / (k! (n − k)!)
C(n, k) = n! / (k! (n − k)!)
Искомое — C. Обратный ход «найти n по C» страница не делает. Считать через три факториала можно, но при больших k удобнее произведение k дробей, как внутри движка.
Не размещения и не бином-значение
Не кортежи с порядком. Не мультимножества с повтором вида. Не число (a+b)ⁿ: там сумма всех C. Не вероятность k успехов — там ещё p. Не C_n = C(2n,n)/(n+1): там один индекс и деление на n+1.
Как пользоваться
Запас n, размер комитета k. Получите, сколькими способами выбрать состав без ролей. Если у членов будут должности — сначала C, потом умножить на перестановку ролей, или сразу P.
Примеры
1. Два из пяти. 10.
2. Симметрия. C(5,3) = 10.
3. Никого. C(10,0) = 1.
4. Всех. C(6,6) = 1.
5. Запрет. k = 5 при n = 4.
Ещё задачи
Лотерея 6 из 36 страница не считает: n = 36 > 20. Разложите вручную или сузьте учебный пример до C(10,3) = 120.
Рука из 5 карт колоды 52 — снова n велико. Учебно C(8,3) = 56 как «короткая колода».
Связь с P: выбрать пару, затем назначить капитана: C(n,2)×2 = P(n,2).
Три пирожных из шести сортов без двух одинаковых — сочетания. С повтором сорта — сосед мультимножеств.
Не кладите p вероятности в k.
Треугольник Паскаля: строка n, клетка k. Страница клетку считает, треугольник не рисует.
C(n,1) = n. C(n,2) = n(n−1)/2 — число рёбер полного графа, не эта геометрия, но проверка: C(5,2) = 10.
Две доли k и n−k дают то же C(n,k): 4!/(3!1!) = 4 = C(4,3).
Комитет с обязательным Иваном: зафиксируйте его, считайте C(n−1, k−1) в тетради, страница флага «обязателен» не имеет.
Одна размерность: число способов, не рубли.
Симметрия C(n,k)
Чертёж: мешок из n шаров, рука берёт k, ярлыков порядка нет. Стрелка «дополнить до n−k» — то же число.
Памятка: набор, не очередь.
Хаб комбинаторики рядом с биномом, потому что коэффициенты — это C.
Итог: k ≤ n, пустое 1, симметрия.
Комитет и карты
Пять человек, двоих в комиссию без ролей: 10. С председателем и секретарём из той же пятёрки: уже P(5,2) = 20.
Покерные «сколько стартовых рук» в полном виде не влезают в лимит 20. Оставьте олимпиадный фрагмент.
Родитель математика. Сосед по коэффициенту в разложении: бином Ньютона.
Итог журнала: C = n!/(k!(n−k)!), без порядка, без повтора элемента.
Контроль: 10; 10; 1; 1. k > n нельзя.
Пример: C(8,2) = 28 пар из восьми.
Не подставляйте 8².
Рабочий пример: C(9,4) = 126. Четверо в команду из девяти заявок.
Связь с 2^n: сумма всех C(n,k) = 2^n. Страница одну клетку, не сумму строки.
Итог для отчёта: размер множества, размер подмножества, частное факториалов.
Финальный якорь: C(5,2) = 10. k = 5 при четырёх — ошибка.
Добор: не делите P на k вместо k!.
Ещё якорь: C(7,7) = 1. Взять всех — один состав.
Журнал: две дежурные из 11 без старшей: C(11,2) = 55. Со старшей сменой — P(11,2) = 110.
Не путайте с n^k: там позиции и повтор.
Финальный блок: подмножество, симметрия, n ≤ 20, без лотереи 36.
Ещё контроль: C(6,2) = 15. C(6,4) = 15.
Почему делят на k!? Каждое подмножество посчитали бы k! раз, если бы нумеровали места.
Итог абзаца: выбрать состав, не расставить по стульям.
Связь с n!: знаменатель два факториала, не один.
Два комитета без пересечения — уже другие правила, не одно C.
Финальный добор: C(n,k), не P, не n^k, не (a+b)ⁿ как число.
Отчёт: «десять сочетаний» без 5 и 2 не отличить от P.
Стык с вероятностью: сначала C, потом × p^k (1−p)^{n−k}.
Не кладите 2,5 в n.
Якорь: 10; симметрия 10; 1; 1. k > n нельзя.
Приложение: три задачи из десяти в варианте, порядок сдачи не важен: C(10,3) = 120. Если номера билетов в очереди — P(10,3).
Одинаковые объекты в списке n ломают «различные элементы»: тогда мультиномиал.
Повторный расчёт после исключения объекта: C(n−1, k) или C(n−1, k−1) по условию «он выбыл / он обязателен».
Контрольная запись: C(n,k) = n (n−1) … (n−k+1) / k!. Для пары это n(n−1)/2. Так 10 = 5×4/2 без трёх факториалов целиком. Симметрия: не выбирать двоих всё равно что выбрать троих оставшихся из пяти.
Типичные ошибки
- Оставить порядок и получить P.
- Забыть симметрию и считать C(n,k) и C(n,n−k) разными ответами задачи.
- Подставить n^k.
- k > n.
- Ждать лотерею 36 из 36 внутри лимита 20.
Соседи: размещения, факториал, бином, мультимножества, биномиальная вероятность.
Итог добора: неупорядоченные подмножества, C = n!/(k!(n−k)!), k ≤ n ≤ 20.
Частые вопросы
- Сколько сочетаний из 5 по 2?
- C(5,2) = 10. Столько же, сколько C(5,3).
- Почему C(n,0) = 1?
- Пустое подмножество одно. C(n,n) = 1: взять всех.
- Если важен порядок вызова?
- Размещения P(n,k). P = C · k!.
- Это коэффициенты бинома?
- Да, C(n,k) стоят в (a+b)ⁿ. Здесь считают одно C, не всю сумму.
- k больше n?
- Ошибка. Подмножество не длиннее множества.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).