Математика / Графы, логика

Сочетания с повторениями: метод звёзд и перегородок

Формула считает наборы из k элементов n видов, когда один вид разрешено выбирать несколько раз, а порядок выбора не важен. Эквивалентная задача — распределить k одинаковых предметов по n различимым ящикам.

Опубликовано: 16 октября 2026 г.Обновлено: 16 октября 2026 г.

Формула

\overline C_n^k=\binom{n+k-1}{k}=\frac{(n+k-1)!}{k!(n-1)!}

Схема Как набор превращается в строку

Две звезды, две перегородки и ещё две звезды кодируют количества (2, 0, 2).

Обозначения

$n$: число доступных видов или подписанных ящиков, безразмерная величина
$k$: общее число выбираемых элементов, безразмерная величина
$xᵢ$: количество элементов i-го вида, безразмерная величина
$C̅$: число возможных наборов, безразмерная величина

Условия применения

Требуются целые n≥1 и k≥0. Элементы одного вида неразличимы, виды различимы, порядок внутри набора не учитывается. Каждый вид доступен в количестве не меньше k. В эквивалентном уравнении каждое xᵢ может принимать любое неотрицательное целое значение.

Ограничения

Верхние ограничения на число элементов каждого вида нарушают простую формулу: нужны вычитание запрещённых вариантов или производящие функции. Если все виды должны присутствовать, сначала выделите по одному элементу каждому виду. Для различных предметов, распределяемых по ящикам, ответ обычно другой.

Подробное объяснение

Набор полностью задаётся числами x₁,…,xₙ: сколько раз выбран каждый вид. Они неотрицательны и в сумме дают k. Перестановка порядка покупки не создаёт нового набора, поэтому правило произведения nᵏ здесь обычно завышает ответ.

Изобразим выбранные элементы k одинаковыми звёздами, а границы между видами — n−1 перегородкой. Количество звёзд до первой перегородки равно x₁, между первой и второй — x₂, после последней — xₙ. Соседние перегородки означают нулевое количество соответствующего вида.

Всего получается k+n−1 позиций. Достаточно выбрать k мест под звёзды; остальные займут перегородки. Каждому набору соответствует ровно одна такая строка, поэтому получаем биномиальный коэффициент C(n+k−1,k). Можно равноправно выбирать n−1 мест под перегородки.

Если требуется xᵢ≥1 для всех i, положим yᵢ=xᵢ−1. После обязательной выдачи n предметов остаётся k−n предметов, и при k≥n ответ равен C(k−1,n−1). При k<n положительных решений нет.

Нулевой размер набора даёт единственный пустой набор: C(n−1,0)=1. При одном виде независимо от k тоже существует один выбор. В обоих случаях формула согласуется с содержанием задачи, включая соглашение 0!=1.

Как пользоваться формулой

Установите, что предметы одного вида неразличимы и порядок выбора не должен создавать новый вариант.
Обозначьте числом n количество видов, а числом k — размер набора; не меняйте эти роли местами в условии.
Проверьте запас каждого вида и допустимость нулевых количеств; при обязательном присутствии выделите по одному.
Вычислите C(n+k−1,k), выбирая позиции звёзд, и проверьте ответ на маленьком наборе прямым перечислением.

Историческая справка

Метод звёзд и перегородок — наглядный язык для классического подсчёта мультимножеств и целых решений. Он связывает задачи распределения с биномиальными коэффициентами: разные внешние сюжеты переводятся в выбор позиций одинаковых символов. В современной учебной традиции XXI века, например в открытом учебнике Оскара Левина Discrete Mathematics: An Open Introduction, этот переход используется как самостоятельное доказательство, а не как правило для запоминания. Справочная линия NIST рассматривает биномиальные коэффициенты через решётчатые пути и тождества; тем самым тот же коэффициент связывает несколько моделей. Название stars and bars описывает выбранную картинку доказательства. Оно само по себе не устанавливает дату первого решения задач распределения или единственного изобретателя метода.

Историческая линия формулы

Здесь применяется классический метод кодирования мультимножеств звёздами и перегородками. Его не следует приписывать автору современного учебника: учебник даёт доступное доказательство общего комбинаторного соответствия, а не заявляет приоритет открытия формулы.

Пример

Нужно выбрать четыре пирожных из трёх видов; каждого вида достаточно, порядок в коробке не важен. Здесь n=3, k=4, поэтому число наборов равно C(3+4−1,4)=C(6,4)=15. Набор из двух пирожных первого вида, нуля второго и двух третьего кодируется строкой **||**: четыре звезды и две перегородки. Проверим ответ по количеству первого вида. Если оно равно 0, оставшиеся четыре распределяются между двумя видами пятью способами; далее получаем 4, 3, 2 и 1 способ. Сумма 5+4+3+2+1=15 подтверждает формулу. Ответ считает состав коробки; разные порядки укладки не добавляют вариантов.

Частая ошибка

Не используйте nᵏ: это число упорядоченных последовательностей выборов. Не ставьте n перегородок: между n видами нужны n−1 границ. Не требуйте незаметно хотя бы один предмет каждого вида. Не применяйте формулу при малом запасе одного сорта, не вычтя наборы, которые этот запас превышают.

Практика

Задачи с решением

Пять жетонов

Условие. Распределите пять одинаковых жетонов по четырём подписанным коробкам; пустые допустимы.

Решение. n=4, k=5. Число распределений C(8,5)=56.

Ответ. 56 распределений

Каждому хотя бы один

Условие. Раздайте восемь одинаковых конфет трём детям так, чтобы каждый получил хотя бы одну.

Решение. После выдачи по одной остаётся 5 конфет. Неотрицательные остатки распределяются C(3+5−1,5)=C(7,5)=21 способом.

Ответ. 21 распределение

Дополнительные источники

https://discrete.openmathbooks.org/dmoi4/sec_counting-multisets.html
https://dlmf.nist.gov/26.3

Связанные формулы

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Перестановки с повторениями: одинаковые элементы

$P=\frac{n!}{n_1!n_2!\cdots n_r!},\qquad n_1+\cdots+n_r=n$

Число различных упорядоченных записей из заданного набора элементов, среди которых есть одинаковые. Формула делит все перестановки на перестановки внутри каждой группы неразличимых элементов.