Явные формулы для количества разбиений

[maxal]

Yadryara в сообщении #1247392 писал(а):

Как, например, из $-{\frac {y+2}{162\, \left( {y}^{2}+y+1 \right) ^{2}}}$ получается $- \frac{1}{162}\,[1,-1,0]_{n\%3}\cdot(n+2)$ ?

Самое простое - разложить в ряд и "увидеть глазами":

? (y+2)/(y^2+y+1)^2 + O(y^20)
%1 = 2 - 3*y + 5*y^3 - 6*y^4 + 8*y^6 - 9*y^7 + 11*y^9 - 12*y^10 + 14*y^12 - 15*y^13 + 17*y^15 - 18*y^16 + 20*y^18 - 21*y^19 + O(y^20)

Или, если действовать строго, то можно и вывести:

$$\frac{y+2}{(y^2+y+1)^2} = \frac{(y+2)(1-y)^2}{(1-y^3)^2} = (2-3y+y^3)\sum_{k\geq 0} (k+1) y^{3k} = \sum_{k\geq 0} (2(k+1)+k) y^{3k} - \sum_{k\geq 0} (3k+3) y^{3k+1},$$

откуда видно, что коэффициент при $x^n$ зависит от $n\%3$. В частности, для $n=3k$ в качестве коэффициента при $x^n$ получаем $2(k+1) + k = 3k+2 = n+2$.

[Yadryara]

Покорно благодарю. Слишком сложным, всё же, получается полином в общем виде. Если $k>4$, то $P(k, n)=$

$$\dfrac1{(k-1)!k!}n^{k-1} + \frac{k^3 - 4k^2 + 3k}{4(k-1)!k!}n^{k-2}+ \frac{9k ^ 6 - 85k ^ 5 + 267 k ^ 4 - 343 k ^ 3 + 156 k ^ 2 - 4k}{288(k-1)!k!}n^{k-3}+ ...$$

В частности, если $k=40$, то видим такие старшие коэффициенты:

$$P(40, n)=\dfrac{n^{39} + 14430n^{38} + 100075755n^{37} + ... }{39!40!}$$

[maxal]

Yadryara, то есть, вы теперь спрашиваете, как получить в общем виде коэффициент при $n^{k-i}$ в $P(k,n)$ как полиноме от $n$ для заданного $i\geq 1$?

[Yadryara]

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

Кстати, заметил закономерности. Степень соответствующих внутренних полиномов увеличивается на $3$, имеется строгая знакопеременность их коэффициентов, а также обнуление их суммы:

$i=2. \qquad 1-4+3 = 0$

$i=3. \qquad 9-85+267-343+156-4 = 0$

То есть для $i=4$ ожидается знакочередующийся полином $b_9k^9 + b_8k^8 + ... + b_1k$, для которого $\sum_{j=1}^9 b_j =0$.

[Yadryara]

ravnovesie в сообщении #1238985 писал(а):

Всё это время этой задачкой болел.

Я не то чтобы болел, но вычисления решил не бросать. Мощностей любимого Бэйсика не всегда хватает, так что начал потихоньку осваивать PARI/GP. Считал при помощи и того, и другого. И вот что у меня получилось.

Yadryara в сообщении #1247856 писал(а):

То есть для $i=4$ ожидается знакочередующийся полином $b_9k^9 + b_8k^8 + ... + b_1k$, для которого $\sum_{j=1}^9 b_j =0$.

Да, всё так и есть:

$$\frac{3k^9 - 49k^8 + 306k^7 - 946k^6 + 1539k^5 - 1273k^4 + 456k^3 - 36k^2}{1152(k-1)!k!}n^{k-4}$$

Постоянный множитель $\frac1{(k-1)!k!}$ можно вынести за скобки в самое начало общего полинома.

Кроме того, подтвердилась ещё одна закономерность. Сумма модулей всех коэффициентов, делённая на знаменатель, равна $i$:

$$\frac{1+4+3}{4} = 2$$

$$\frac{9+85+267+343+156+4}{288} = 3$$

$$\frac{3+49+306+946+1539+1273+456+36}{1152} = 4$$

Есть и ещё кое-какие наблюдения.

[Yadryara]

Да, я в курсе, что "размещение большого числа сообщений в пределах одной темы подряд" является нарушением Правил форума.

Но, ввиду того, что найденные закономерности, видимо, являются новыми и ранее нигде не публиковались, мне разрешили продолжать сообщать о своих находках.

Для $i=5$:

$\frac{675+16650+167575+902062 + 2845365 + 5400990 + 6087525 + 3871986 + 1262060 + 175160 + 4800 + 1152}{4147200}=5$

Все ранее найденные свойства подтвердились. Есть и ещё кое-что. Например, можно заметить, что $\frac{675}{4147200} = \frac1{6144}$

Старшие коэффициенты, то есть при $k^{3i}$ численно равны

$$\frac11; \frac14; \frac1{32}; \frac1{384}; \frac1{6144};... \frac1{4^{i-1}(i-1)!}$$

Позже расскажу, как этим пользоваться на практике, то есть находить точные и приблизительные количества разбиений для различных $k$ и $n$.

[Yadryara]

Итак, допустим что нам надо разбить целое неотрицательное число $n$ ровно на $5$ частей. Сколькими способами можно это сделать? Подставив $k=5$ в вышеприведённую формулу, получим

$$\frac{n^4 + 10n^3 + 10n^2 - 75n - 61.6(3)}{2880}$$

Формула эта приблизительная, поскольку первые три коэффициента в ней точные, а вот последние два — средневзвешенные. Ибо существуют $16$ различных точных формул для всех остатков от деления $n$ на $60$.

В данном случае вполне можно применить нехитрый приём и получить формулу уже для всех целых неотрицательных $n$.

$$\left[\frac{n^4 + 10n^3 + 10n^2 - 15(5+3(-1)^n)n}{2880}\right]$$

А если подставим $k=4$, то придём к формуле, которая тоже годится для всех целых неотрицательных $n$.

$$\left[\frac{2n^3 + 6n^2 - 9(1-(-1)^n)n}{288}\right]$$

Соответствующие последовательности A001401 и A001400.

[maxal]

Yadryara в сообщении #1247856 писал(а):

Степень соответствующих внутренних полиномов увеличивается на $3$, имеется строгая знакопеременность их коэффициентов, а также обнуление их суммы:

Обнуление суммы коэффициентов ожидаемо. Дело в том, что сумма коэффициентов равна $P(1,k)$, а это по определению ноль при $k>1$.

[Yadryara]

Сколькими способами можно разбить число $n$ ровно на $k$ натуральных слагаемых, не превышающих $m$?

Обозначил искомое количество разбиений $P(n, k, m)$ и сделал ряд наблюдений. Не знаю, какие вещи из нижесказанного тривиальны.

1. Для $0 \leqslant n \leqslant k(m + 1)$

$P(n, k, m) = P(k(m + 1) - n, k, m)$


2. Пусть $x = k - m + 1$, тогда

$P(n, k, m) = P(n - x, k - x, m + x)$


В частности, для обеих вариантов той самой задачи Арнольда:

$P(54, 11, 10) = P(67, 11, 10) = P(52, 9, 12) = P(65, 9, 12) = 4447$

$P(65, 11, 11) = P(67, 11, 11) = P(64, 10, 12) = P(66, 10, 12) = 9673$


3. $\sum\limits_{n=k}^{km}P(n, k, m) = \binom{k+m-1}{k}$

То есть это сумма всех ненулевых $P(n, k, m)$ для заданных $k$ и $m$, например, $\sum\limits_{n=9}^{108}P(n, 9, 12) = \binom{20}{9} = 167960$


4. Максимум для $P(n, k, m)$ достигается при $n = \lfloor \frac{k(m + 1)}2\rfloor$ и для нечётных $m$ точно равен значениям в соответствующих столбцах A183917.

Например, для $P(n, 11, 11)$, максимум достигается при $n=66$ и равен $9686$.

Если кто-то знает подробности про A183917, милости прошу...

[wrest]

Ну, чтоб не пропало, оставлю тут.

Подсчеты на PARI/GP

Количество разбиений целого неотрицательного (натурального) числа n на слагаемые:
N=numbpart(n)
Количество разбиений числа n на k или меньше слагаемых:
N=#partitions(n,,k) или N=#partitions(n,,[1,k])
Количество разбиений числа n на k или больше слагаемых:
N=#partitions(n,,[k,n])
Количество разбиений числа n ровно на k ненулевых слагаемых:
N=#partitions(n,,[k,k])
Количество разбиений числа n на слагаемые, каждое из которых больше или равно k:
N=#partitions(n,[k,n])
Количество разбиений числа n на слагаемые, каждое из которых меньше или равно k:
N=#partitions(n,[1,k])

Количество разбиений числа n на слагаемые, где каждое слагаемое больше или равно amin и меньше или равно amax, а количество слагаемых больше или равно kmin, и меньше или равно kmax:
N=#partitions(n,[amin,amax],[kmin,kmax])

Если убираем решетку # перед patitions, то получаем сами эти разбиения в виде набора одномерных массивов (векторов) чисел-слагаемых.

[Yadryara]

Возвращался к явным формулам при обсчёте подзадач из темы «Сложная числовая задача (6 класс)»
Есть кое-что новое.

Формулу в общем виде запишу так:

$P(k, n)=$

$$\dfrac1{(k-1)!k!}\left(n^{k-1} + \frac{k^3 - 4k^2 + 3k}{4}n^{k-2}+ \frac{9k ^ 6 - 85k ^ 5 + 267 k ^ 4 - 343 k ^ 3 + 156 k ^ 2 - 4k}{288}n^{k-3}+ ...\right)$$

Введу обозначения

$$\dfrac1{(k-1)!k!}\left(n^{k-1} + (A_2k^3 + B_2k^2 + ...)n^{k-2}+ (A_3k^6 + B_3k^5 + ...)n^{k-3}+ ...\right)$$

$$\dfrac1{(k-1)!k!}\sum_{i=1}^k (A_ik^{3(i-1)} + B_ik^{3(i-1)-1} + ...)n^{k-i}$$

Ранее было получено, что

$$A_i = \frac1{4^{i-1}(i-1)!}$$

Введу $b_i = \frac{B_i}{A_i }$. Тогда

$$\dfrac1{(k-1)!k!}\sum_{i=1}^k\frac{ k^{3(i-1)} + b_ik^{3(i-1)-1} + ...}{4^{i-1}(i-1)!}n^{k-i}$$

Где значение

$$b_i = \frac{13i^2 + 33i - 46}{-18}$$

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