Число упорядоченных разбиений числа k на слагаемые <= n

[the_mescalito]

Пожалуйста наведите на мысль.

Необходимо найти число упорядоченных разбиений натурального числа k на положительные натуральные слагаемые, не превосходящие n (n<k).

Н-р, для k=4, n=2 нужны разбиения: (1,1,1,1); (1,1,2); (1,2,1); (2,1,1); (2,2).

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

Индукция по $k$.

Пусть $s(k,n)$ --- требуемое число разбиений. Тогда $s(1,n)=1$ и

$$ s(k+1,n) = \delta_{k,n} + \sum_{i=1}^{\min\{k,n\}} s(k+1-i,n), $$

где

$$ \delta_{k,n} = \begin{cases} 1, &k+1 \leqslant n; \\ 0, &k+1 > n \end{cases} $$

Для практического подсчёта эта формула наиболее удобна. Можно ли её привести к какому-нибудь "более приемлемому" виду --- не знаю. Возможно, что и нет.

Добавлено спустя 29 минут 21 секунду:

Лучше даже с нуля начинать, тогда формулы будут покрасивше.

Имеем $s(0,n)=1$ для любого $n > 0$ и

$$ s(k,n) = \sum_{i=1}^{\min\{k,n\}} s(k-i,n) $$

Получается, что дельты уже не нужны.

[the_mescalito]

А как оценить в этой рекурсивной формуле зависимость s от k? Она полиномиальна или экспоненциальна?..

[Trotil]

Я решал похожую задачу, правда (1,1,2); (1,2,1); (2,1,1) считал за одно разбиение. Помнится, получить явную формулу у меня получилось.

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

the_mescalito писал(а):

А как оценить в этой рекурсивной формуле зависимость s от k? Она полиномиальна или экспоненциальна?..

При больших $k$ сумма при вычислении $s(k+1,n)$ будет состоять из $n$ слагаемых. То есть для фиксированного $n$ при данном $k$ при вычислении $s(k,n)$ нужно выполнить порядка $n \cdot k$ сложений.

Получается линейная зависимость от $k$ и экспоненциальная от длины двоичной записи $k$.

Но, кстати, я подозреваю, что $s(k,n)$ по величине растёт экспоненциально с ростом $k$. Так что экспоненциальная зависимость времени вычисления $s(k,n)$ от длины двоичной записи $k$ будет иметь место при любом алгоритме вычисления $s(k,n)$.

[the_mescalito]

Trotil
А как Вы решали свою задачу? Можете припомнить?

[Trotil]

the_mescalito
Припоминаю, что аналогично, как и Профессор Снэйп. То есть через реккуренты.

[the_mescalito]

Профессор Снэйп писал(а):

$$ s(k+1,n) = \delta_{k,n} + \sum_{i=1}^{\min\{k,n\}} s(k+1-i,n), $$

А Вы не могли бы пояснить на пальцах, как эта формула получается?
Откуда дельта мне понятно.. А откуда все

$$s(k+1-i,n)$$

берутся?

[maxal]

Ответом также будет коэффициент при $x^k$ в разложении

$$\sum_{t=0}^{\infty} (x+x^2+\dots+x^n)^t = \frac{1}{1-x\frac{1-x^n}{1-x}} = \frac{1-x}{1-x(2-x^n)}$$

Отсюда можно получить явную формулу:

$$s(n,k)=f(n,k)-f(n,k-1),$$

где $f(n,k)$ - это коэффициент при $x^k$ в разложении $\frac{1}{1-x(2-x^n)}$:

$$f(n,k)=\sum_{j=0}^{\lfloor k/(n+1)\rfloor} {k-nj\choose j} (-1)^j 2^{k-(n+1)j}$$