Сколько различных слов при заданных кратностях букв
n букв всего, i-я буква встречается nᵢ раз, n = сумма nᵢ. Разные перестановки неразличимых копий не считают. Раздел: комбинаторика.
Контроль: [2,2,2] → 90. [3,1] → 4. [1,1,1] → 6 = 3!. [5,0] → 1.
Долей хотя бы две, каждая целая 0…20, сумма ≤ 20. Родитель математика.
M = n! / (n₁! n₂! …)
M = n! / (n₁! n₂! …)
Список nᵢ, сумма n и число долей m страница показывает как пояснение. Искомое — M. Добавляйте строки списка, если видов больше двух.
Не n^k всех слов
Не алфавит в степень: там любой состав. Не P(n,k) без заданных кратностей. Не сколько составов бывает — здесь состав введён. Не значение (a+b)ⁿ хотя коэффициент C(n,k) — частный случай двух долей.
Как пользоваться
Впишите кратности букв или размеры групп. Сумма станет n. Получите, сколькими способами нарезать n позиций на эти группы. Две доли — проверка через C.
Примеры
1. Три двойки. 90.
2. Бином. 3+1 → 4.
3. Все по одному. 3! = 6.
4. Нулевая доля. [5,0] → 1.
5. Запрет. доля 21.
Ещё задачи
Анаграмма слова с буквами М₂, И₄, С₄, П₂ — сумма 12 ≤ 20, но четыре двойки миссисипи в учебнике длиннее лимита по факту 11 букв: MISSISSIPPI = 11! / (4!4!2!1!) считайте, если влезет в 20. 11 ≤ 20: введите 4,4,2,1.
Разложить 9 студентов на команды 4, 3, 2: 9!/(4!3!2!) = 1260.
Связь с C: сначала выбрать n₁ мест из n, затем n₂ из остатка — произведение C даёт M.
Все nᵢ = 1: M = n!, полные перестановки различных букв. Сосед n! без списка.
Не кладите само n в список вместо долей: список — части, не итог.
Три группы равные [2,2,2] уже в контроле. [3,3,3] сумма 9, M = 1680.
Покрасить 5 клеток в 2 красных и 3 синих: [2,3] = C(5,2) = 10.
Сколько разных векторов кратностей — другой вопрос. Здесь вектор уже дан.
Одна строка списка не допускается: минимум две доли, даже если вторая нуль.
Число способов, не вероятность. Вероятность конкретного состава при независимых буквах — в тетради / n^n.
Анаграммы
Чертёж: n клеток слова, раскраска по цветам с заданным числом клеток каждого цвета.
Памятка: делить n! на факториалы размеров цветов.
Хаб комбинаторики ставит M рядом с C, потому что две доли есть бином.
Итог: список ≥ 2, сумма ≤ 20, нули в доле законны.
Доли и бином
Биномиальный коэффициент C(n,k) = n! / (k! (n−k)!) — полиномиальный с m = 2. Три и больше долей обобщают. Коэффициенты (x₁+…+x_m)^n именно эти M.
Не раскрывайте весь полином: страница одно M для одного набора степеней.
Родитель математика. Сосед по всем словам: n^k при k = n.
Итог журнала: M = n! / ∏ nᵢ!, n = сумма, не P(n,k).
Контроль: 90; 4; 6; 1. Доля 21 нельзя.
Пример: [4,2] → 15 = C(6,4).
Не подставляйте 6^3 для трёх букв без кратностей.
Рабочий пример: [2,2,1] сумма 5, M = 30. Слово из двух а, двух б, одной в.
Связь с P: если все различны, P(n,n) = n! = M.
Итог для отчёта: кратности, сумма, частное факториалов.
Финальный якорь: 2,2,2 → 90. Сумма > 20 нельзя.
Добор: не называйте это «сочетаниями с повторениями» — те считают, сколько векторов (n₁,… ) бывает.
Ещё якорь: [1,1,1,1] = 24 = 4!.
Журнал: флаги из 3 полос, 2 одинаковых цвета и 1 другой: не M без модели «какие цвета». Сначала выберите цвета, потом M для расстановки.
Не путайте с степенью 6²: это не 6! / 2!.
Финальный блок: заданный состав, анаграмма, лимит суммы 20, минимум две доли.
Ещё контроль: [7,1] = 8. [2,3,2] = 210 при сумме 7.
Почему делят на nᵢ!? Перестановки внутри группы одинаковых букв невидимы.
Итог абзаца: нарезать позиции на окрашенные блоки заданных длин.
Связь с биномом Ньютона: коэффициент при a^{n₁} b^{n₂} есть M двух долей.
Два слова подряд (состав1 и состав2) — произведение двух M, если независимы.
Финальный добор: n!/∏nᵢ!, не n^k, не C(n+k−1,k) как число составов, не P без кратностей.
Отчёт: «девяносто анаграмм» без 2,2,2 не проверить.
Стык с C(6,2) цепочкой: C(6,2)×C(4,2)×C(2,2)/1 = 90, делить на перестановку трёх одинаковых размеров групп? У нас размеры равны, осторожно с симметрией цветов. Проще одна формула M.
Не кладите n = 6 отдельным входом: сумма списка сама n.
Якорь: 90; 4; 6; 1. Доля 21 нельзя.
Приложение: раздать 10 одинаковых задач трём авторам пакетами 5, 3, 2 — нет, задачи одинаковые, это звёзды. Если задачи различные — тогда M = 10!/(5!3!2!).
Одинаковые доли не требуют делить ещё на число перестановок долей: формула уже про позиции, не про переименование цветов.
Повторный расчёт после слияния двух видов в один: сложите две nᵢ, список короче, M другое.
Типичные ошибки
- Считать n^n вместо состава.
- Забыть нулевой факториал 0! = 1.
- Класть сумму в список как ещё одну долю.
- Одна доля без второй.
- Сумма > 20.
Соседи: сочетания, факториал, бином, n^k, мультимножества.
Итог добора: коэффициент n! / ∏ nᵢ! при заданных кратностях, сумма долей ≤ 20, две и больше частей.
Частые вопросы
- Сколько слов из букв с кратностями 2, 2, 2?
- n = 6, M = 6! / (2! 2! 2!) = 90.
- Две доли 3 и 1?
- 4! / (3! 1!) = 4, это C(4,3). Полиномиальный с двумя группами есть биномиальный.
- Это число всех паролей длины n?
- n^k считает все слова. Здесь состав букв уже зафиксирован.
- Одна доля 5 и нулевая?
- 5! / (5! 0!) = 1. Нулевая кратность вида «буквы нет».
- Сумма долей больше 20?
- Ошибка. Лимит как у соседних страниц хаба.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).