Количество разбиений натурального числа на слагаемые

[dronbas]

Здравствуйте, не могу понять как решить следующую задачу.
Найти количество разбиений натурального числа $n$ на $k$ неотрицательных натуральных слагаемых, не превосходящих $z$. Разбиения, отличающиеся порядком слагаемых считаются разными.
Если бы не было верхнего ограничения на величину слагаемого, то решение найти не трудно.

[Профессор Снэйп]

$$ N(n,k,z) = \sum_{i=0}^z N(n-i,k-1,z); \,\,\, N(n,1,z) = \text{понятно чему} $$

Похоже на числа Стирлинга второго рода. Наверняка что-нибудь известное.

[Yu_K]

Это будет рекурсивная формула.
Можно использовать также и принцип включения-исключения.

[maxal]

Вычислите коэффициент при $x^n$ в

$$(1+x+x^2+\dots+x^z)^k = (1-x^{z+1})^k (1-x)^{-k}$$

[Yu_K]

maxal
А если считать разбиения одинаковыми, при условии, что они совпадают с точностью до перестановки - есть ли формула для их кол-ва?
(5,2,2)=(2,5,2)=(2,2,5)
(6,2,1)=(6,1,2)=(2,1,6)=(2,6,1)=(1,6,2)=(1,2,6)

[ИСН]

Тогда ещё хуже.

[Профессор Снэйп]

Реккурентная формула для вычисления $N(n,k,z)$ требует порядка $k \cdot n \cdot z$ операций. Не уверен, что "красивая формула" (если она, конечно, существует) даст существенно лучший результат.

[maxal]

Профессор Снэйп
Даст. Этот подход post292008.html#p292008 дает формулу в виде суммы из ~ n/(z+1) слагаемых.

[Профессор Снэйп]

maxal в сообщении #292122 писал(а):

Профессор Снэйп
Даст. Этот подход post292008.html#p292008 дает формулу в виде суммы из ~ n/(z+1) слагаемых.

Я не совсем понимаю, как там делить на $(1+x)^k$.

[maxal]

Профессор Снэйп

$$\sum_{j=0}^{\lfloor n/(z+1)\rfloor} (-1)^{n+zj} \binom{k}{j} \binom{-k}{n-(z+1)j}$$

[Профессор Снэйп]

Я не совсем понял, откуда взялась формула, но даже не это важно. Слагаемые --- биномиальные коэффициенты, а их вычисление тоже требует времени, так что выигрыш в объёме вычислений от этой формулы не очевиден.

[maxal]

Профессор Снэйп в сообщении #292203 писал(а):

Я не совсем понял, откуда взялась формула, но даже не это важно. Слагаемые --- биномиальные коэффициенты, а их вычисление тоже требует времени, так что выигрыш в объёме вычислений от этой формулы не очевиден.

Формула взялась отсюда: post292008.html#p292008
А биномиальные коэффициенты - сущности существующие вне контекста задачи. Можно считать, например, что все они заранее вычислены (до некоторой границы), и задачи с различными параметрами (до той же границы) решаются конвеерно.

[dronbas]

maxal в сообщении #292008 писал(а):

Вычислите коэффициент при $x^n$ в

$$(1+x+x^2+\dots+x^z)^k = (1-x^{z+1})^k (1-x)^{-k}$$

maxal,
расскажите пожалуйста или дайте намёк почему решением задачи является указанный вами коэффцициент?И как вы получили формулу для коэффициента?

[maxal]

dronbas в сообщении #292371 писал(а):

расскажите пожалуйста или дайте намёк почему решением задачи является указанный вами коэффцициент?

Каждой композиции $n=m_1 + m_2 + \dots + m_k$ соответствует произведение $x^{m_1} x^{m_2} \dots x_{m_k}$ в разложении

$$(1+x+x^2+\dots+x^z)(1+x+x^2+\dots+x^z)\dots (1+x+x^2+\dots+x^z)=(1+x+x^2+\dots+x^z)^k$$

где $x^{m_1}$ берется из первой скобки, $x^{m_2}$ - из второй и т.д.

dronbas в сообщении #292371 писал(а):

И как вы получили формулу для коэффициента?

Представляете каждый множитель в произведении $(1-x^{z+1})^k (1-x)^{-k}$ в виде ряда:

$$\sum_{i=0}^\infty (-1)^i \binom{k}{i} x^{i(z+1)} \sum_{j=0}^\infty (-1)^j \binom{-k}{j} x^j = \sum_{i=0}^\infty \sum_{j=0}^\infty (-1)^{i+j} \binom{k}{i} \binom{-k}{j} x^{i(z+1)+j}$$

Нас интересует коэффициент при $x^n$, для которого $i(z+1)+j=n,$ то есть, $j=n- i(z+1)$.

[Yu_K]

А как посчитать варианты разбиений $N= m_1+m_2+...+m_k$ ровно на $k$ слагаемых $m_i > 0$. Понятно что это отличается от случая не более, чем $k$ слагаемых.


Вопрос остался без ответа. Варианты разбиений $N= m_1+m_2+...+m_k$ на не более чем $k$ слагаемых с условием $ 0 \leq m_1 \leq m_2\leq ...\leq m_k \leq z$ можно как то по простому пересчитать?