Кратко — разные постановки дают разные формулы. Ниже — основные случаи, методы и тонкости.
1) Важная дискриминация моделей (что значит «одинаковые коробки» и «предметы различимы»):
- «коробки одинаковые» = unlabeled (перестановки коробок не считаются разными).
- «коробки различимые» = labeled.
- «предметы неразличимы» = считаем разбиения числа $n$ (целые части).
- «предметы различимы» = считаем разбиения множества из $n$ элементов.
Нельзя переводить ответ из одной модели в другую без изменений.
2) Индистинктные предметы (неразличимы), коробки различимые (labeled):
- Требуется число неотрицательных целых решений $x_1+\cdots +x_k=n$ с $x_i\ge m$.
- Подстановка $y_i=x_i-m$ даёт $\sum y_i=n-km$. Если $n<km$ — ноль. Иначе
$$\text{число}=\left(\genfrac{}{}{0ex}{}{n-km+k-1}{k-1}\right).$$ (Классическая «stars and bars».)
3) Индистинктные предметы, коробки одинаковые (unlabeled):
- Это число разбиений целого $n$ на ровно $k$ частей, каждая $\ge m$.
- Нет простого закрытого выражения; удобно через ОГФ:
$$\text{число}=[x^{n-km}]\prod _{i=1}^k\frac{1}{1-x^i},$$ (или сказать: число разбиений $n-km$ на не более чем $k$ частей). Для вычисления используют DP/рекурсии для partition-функции.
4) Различимы предметы, коробки различимые (labeled):
- Нужны функции из $n$-множества в $k$-множество с прообразами размера $\ge m$.
- Формула через экспоненциальные ОГФ / суммирование по векторам размеров:
$$\text{число}=\sum _{\begin{array}{c}{s}_1+\cdots +s_k=n\\ s_i\ge m\end{array}}\frac{n!}{s_1!\cdots s_k!}.$$ - ЭКСП-ОГФ запись:
$$\text{число}=n}^k=n}^k.$$ - Альтернатива — включение–исключение: вычесть распределения, где какая-либо коробка имеет <$m$ элементов (работает, но громоздко).
5) Различимы предметы, коробки одинаковые (unlabeled):
- Это число разбиений множества из $n$ элементов на $k$ неупорядоченных блоков размером $\ge m$.
- Через экспоненциальную ОГФ:
$$\text{число}=n![x^n]\frac{1}{k!}(\sum _{r\ge m}\frac{x^r}{r!}{)}^k.$$ - При $m=1$ это числа Стирлинга второго рода $S(n,k)$. Для общего $m$ — «ограниченные» Стирлинговы числа, вычисляются рекурсивно или через коэффициенты выше.
6) Метод включения–исключения (общая идея):
- Отсчитываем все распределения (без нижней границы), затем вычитаем те, где хотя бы одна коробка нарушает условие $x_i\ge m$. Для разных моделей выражения для |A_S| различаются (в случае различимых предметов удобно суммировать по возможным размерам прообразов в S и т.д.).
7) Тонкости и предупреждения:
- Нельзя просто «разделить на $k!$», чтобы перейти от labeled к unlabeled в случае неразличимых предметов (композиции → разбиения): при равных частях делимость на $k!$ не даёт целого; где части могут совпадать, нужно считать паритеты/симметрии отдельно. Деление на $k!$ корректно для перехода от упорядоченных разбиений множества (labeled blocks) к неупорядоченным, потому что каждое неупорядоченное разбиение соответствует ровно $k!$ упорядоченным.
- Задача «предметы неразличимы, коробки одинаковые» = задача о целочисленных разбиениях — алгоритмически сложнее, нет простого закрытого вида.
- Выбор модели сильно меняет ответ (см. пример ниже).
8) Пример (показывает различия). Пусть $n=3,k=2,m=1$.
- Неразличимые предметы, коробки различимые:
$$\left(\genfrac{}{}{0ex}{}{3-2\cdot 1+2-1}{2-1}\right)=\left(\genfrac{}{}{0ex}{}{2}{1}\right)=2\text{(композиции:}(1,2),(2,1)\text{)}.$$ - Неразличимые предметы, коробки одинаковые:
$$1\text{(разбиение числа}3\text{на 2 части:}2+1\text{)}.$$ - Различимые предметы, коробки различимые (суръекции, $m=1$):
$$\sum _{j=0}^2(-1{)}^j(\genfrac{}{}{0ex}{}{2}{j})(2-j{)}^3=2^3-2\cdot 1^3=6.$$ - Различимые предметы, коробки одинаковые:
$$S(3,2)=3.$$ Итого — четыре разные цифры $2,1,6,3$.
9) Как выбирать метод на практике:
- Если предметы неразличимы и коробки различимые → звёздочки-полоски (closed form).
- Если предметы различимы → использовать EGF/суммы по размерам либо включение–исключение; для численного подсчёта — суммирование по композициям или DP/FFT для извлечения коэффициентов.
- Если коробки одинаковые и предметы неразличимы → задачи разбиений: DP/числа partition.
- Для программной реализации: динамика по сумме/числу блоков; для больших $n,k$ — аккуратно использовать EGF/комбинаторные формулы и численные методы для коэффициентов.
Если нужно, могу привести код (DP/генераторы коэффициентов) для любой конкретной из четырёх моделей.