Сколько мультимножеств размера k из n видов
Вид можно брать несколько раз, порядок в корзине не нумеруют. Классика «звёзды и перегородки»: C(n+k−1, k). Раздел: комбинаторика.
Контроль: n = 5, k = 3 → 35. n = 3, k = 1 → 3. k = 0 → 1. n = 2, k = 2 → 3. n = 0 и k = 2 — отказ.
n, k целые 0…20. Родитель математика.
C(n + k − 1, k)
C(n + k − 1, k)
То же, что C(n+k−1, n−1) при n ≥ 1. Искомое — число составов. Не путайте поле n с «уже n+k−1» — движок сам сдвинет.
Не обычные сочетания
Не C(n,k) без повтора. Не очередь без повтора. Не слова n^k. Не коэффициент при фиксированных nᵢ — там состав уже выбран.
Как пользоваться
n — сколько сортов в витрине, k — сколько штук кладёте в пакет, сорт можно повторять, «две булочки с маком» не отличаются порядком в пакете. Получите число разных пакетов.
Примеры
1. Пять видов, три штуки. 35.
2. Один из трёх. 3.
3. Ничего. 1.
4. Два из двух. 3: (2,0), (1,1), (0,2).
5. Запрет. видов 0, штук 2.
Ещё задачи
Неотрицательные целые x+y+z = 4: это n = 3 вида слагаемых, k = 4 единиц. C(3+4−1, 4) = 15. Страница не вводит x,y,z полями — только n и k.
Мороженое 4 шара, 6 вкусов, шары не упорядочены: C(6+4−1, 4) = 126, но 6+4−1 = 9 ≤ 20, C(9,4) = 126.
Связь с C: формула сводит задачу к одному обычному сочетанию большего верха.
Если шары в рожке сверху вниз различны как слои — уже n^k или P, не эта страница.
Не кладите сумму n+k−1 в поле n.
Два вида и k штук: k+1 способ (сколько первого, остальное второе). Проверка n = 2 k = 2 → 3.
Карточки «любое число копий типа»: мультимножество. Один экземпляр типа — обычные C.
Факториал входит внутрь C(n+k−1, k), отдельно не жмите.
Ограничение «не больше двух маковых» — не чистая формула, включение-исключение в тетради.
Число способов — безразмерное.
Звёзды и перегородки
Чертёж: k звёзд в ряд, n−1 перегородок. Число позиций звёзд и палок C(n+k−1, k).
Памятка: повтор вида, без порядка пакета.
Хаб комбинаторики отделяет это от C(n,k), чтобы не забыть «плюс k минус один».
Итог: n видов, k штук, пустой пакет 1, пустая витрина с покупкой нельзя.
Пирожки и уравнения
Уравнение x₁+…+x_n = k в целых ≥ 0 — буквально эта модель. xᵢ ≥ 1 сводят сдвигом: yᵢ = xᵢ−1, тогда k' = k−n, если k ≥ n. Сдвиг делайте в тетради, страница ждёт уже неотрицательную постановку.
Пирожковая витрина и «три любые»: мультимножество. «Три в очередь к кассе» — n^k.
Родитель математика. Сосед по составу, когда кратности уже известны: M.
Итог журнала: C(n+k−1, k), не C(n,k), не n^k.
Контроль: 35; 3; 1; 3. Пустая витрина с k > 0 нельзя.
Пример: n = 4 k = 2 → C(5,2) = 10.
Не подставляйте 4² = 16: это порядок.
Рабочий пример: n = 8 k = 3 → C(10,3) = 120 пакетов по три с повтором сорта.
Связь с n^k: каждое мультимножество {два а, одно б} порождает несколько слов — как раз мультиномиал 3!/(2!1!) = 3 слова.
Итог для отчёта: виды, штуки, сдвиг верха n+k−1.
Финальный якорь: 5 видов × 3 штуки → 35. Нулевые виды и ненулевые штуки нельзя.
Добор: не называйте это «размещениями с повторениями» — то про порядок.
Ещё якорь: n = 1 любое k → 1. Один сорт, сколько ни бери, пакет один.
Журнал: канцелярия 3 типа стикеров, берёте 5 листов: C(3+5−1,5) = 21.
Не путайте с P: там вычитают, не прибавляют k.
Финальный блок: мультимножество, звёзды, n,k ≤ 20, без верхних квот на xᵢ.
Ещё контроль: n = 5 k = 1 → 5. n = 5 k = 5 → C(9,5) = 126.
Почему n−1 перегородок? n урн, между ними n−1 стенок. Звёзды — единицы товара.
Итог абзаца: разложить k неразличимых единиц по n ящикам.
Связь с C(n,k): при k ≤ n и запрете повтора вернитесь на ту страницу.
Две витрины (сладкое и солёное отдельно) — два расчёта, произведение, если пакеты независимы.
Финальный добор: C(n+k−1,k), не P, не n^k, не обычное C(n,k).
Отчёт: «тридцать пять пакетов» без 5 и 3 не отличить от C(7,3) в другой задаче.
Стык с биномом: коэффициент C(n+k−1, k) иногда пишут в производящей (1−x)^{−n}, страница ряд не суммирует.
Не кладите 7 в n, если видов было 5, а 7 — уже n+k−1.
Якорь: 35; 3; 1; 3 способа для двух видов и двух штук. Пустая витрина с покупкой нельзя.
Приложение: набор монет на сумму не эта модель: номиналы разные веса. Здесь единицы одинаковые, ящики — виды.
Отрицательные xᵢ нет. Ноль в ящике можно: не взяли этот сорт.
Повторный расчёт после добавления сорта: n выросло, k то же, C новое.
Типичные ошибки
- Считать C(n,k) без сдвига.
- Путать с n^k.
- Класть n+k−1 в поле n.
- n = 0 и k > 0.
- Думать, что порядок в пакете важен.
Соседи: сочетания, n^k, размещения, полиномиальный коэффициент, факториал.
Итог добора: мультимножества размера k из n видов, C(n+k−1, k), без квот на кратность.
Частые вопросы
- Сколько способов взять 3 предмета из 5 видов с повтором, порядок не важен?
- C(5+3−1, 3) = C(7,3) = 35.
- k = 0?
- 1: пустое мультимножество. n = 0 и k > 0 — ошибка.
- Это C(n,k)?
- Обычные сочетания запрещают повтор элемента. C(5,3) = 10, не 35.
- Если порядок важен и повтор можно?
- n^k. 5³ = 125.
- Где полиномиальный коэффициент?
- n! / n₁! n₂! … считает слова с уже заданными кратностями, не число составов.
- Где хаб?
- Комбинаторика.
Источники
- Школьная комбинаторика: P(n,k) = n!/(n−k)!, C(n,k) = n!/(k!(n−k)!), размещения с повторениями n^k, сочетания с повторениями C(n+k−1, k), полиномиальный коэффициент n!/(n₁! n₂! …).