2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Число упорядоченных разбиений числа k на слагаемые <= n
Сообщение06.05.2008, 22:10 
Пожалуйста наведите на мысль.

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

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

 
 
 
 
Сообщение06.05.2008, 22:54 
Аватара пользователя
Индукция по $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)
$$

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

 
 
 
 
Сообщение07.05.2008, 08:54 
А как оценить в этой рекурсивной формуле зависимость s от k? Она полиномиальна или экспоненциальна?..

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

 
 
 
 
Сообщение07.05.2008, 09:40 
Аватара пользователя
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)$.

 
 
 
 
Сообщение07.05.2008, 09:50 
Trotil
А как Вы решали свою задачу? Можете припомнить?

 
 
 
 
Сообщение07.05.2008, 10:14 
Аватара пользователя
the_mescalito
Припоминаю, что аналогично, как и Профессор Снэйп. То есть через реккуренты.

 
 
 
 
Сообщение07.05.2008, 10:40 
Профессор Снэйп писал(а):
$$
s(k+1,n) = \delta_{k,n} + \sum_{i=1}^{\min\{k,n\}} s(k+1-i,n),
$$


А Вы не могли бы пояснить на пальцах, как эта формула получается?
Откуда дельта мне понятно.. А откуда все $$s(k+1-i,n)$$ берутся?

 
 
 
 
Сообщение09.05.2008, 03:24 
Аватара пользователя
Ответом также будет коэффициент при $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}$$

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group