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

[Yadryara]

Настоящая тема является продолжением обсуждения вот этой темы. Опубликовано отдельно с учётом пожелания grizzly.

Итак, сколькими способами можно разбить натуральное $n$ на $k$ ненулевых натуральных слагаемых? Разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми.

Пока есть такие соображения. Если $k>2$, то

$$P(k, n)=\left[\frac{4n^{k-1} + (k^3 - 4k^2 + 3k)n^{k-2}+ ... + a_1n}{4(k-1)!k!}\right]$$

В частности, если $k=7$ и $n$ кратно $6$, то точная формула, видимо, такова:

$$P(7, n)=\left[\frac{n^6 + 42n^5 + 560n^4 + 1960n^3 - 11088n^2 - 100800n}{3\;628\;800}\right]$$

А ежели $k=8$ и $n$ кратно $12$, то

$$P(8, n)=\left[\frac{n^7 +70n^6 + 1743n^5 + 17150n^4 + 31416n^3 - 317520n^2 - 120960n}{203\;212\;800}\right]$$

Для других $n$ точные формулы получаются корректировкой младшей степени соответствующего полинома.

Вкратце. Пользуясь рекуррентным соотношением, вычислял на компе много разбиений $P(k,n)$, затем применял прямую интерполяционную формулу Ньютона для соответствующего интервала между соседними значениями $n$. Например, для $k=8$ пришлось брать интервал $n_i-n_{i-1}=840$

Вопрос о формуле в общем виде пока остаётся открытым. По крайней мере, в OEIS есть только формулы до $k=6$ включительно.

[maxal]

В терминах стандартной функции разбиений $q(n,k)$ имеем:

$$P(k,n) = q(n,k) - q(n,k-1) = q(n-k,k).$$

Явные значения $q(n,k)$ для малых $k$ можно получить из рекуррентной формулы:

$$q(n,k) = q(n,k-1) + q(n-k,k),$$

из которой для $k>1$ следует

$$q(n,k) = \sum_{i=0}^{\lfloor (n-1)/k\rfloor} q(n-ik,k-1).$$

Стартуя с $q(n,1) = 1$, получаем:

$$q(n,2) = \lceil \frac{n+1}{2} \rceil$$

$$q(n,3) = \sum_{i=0}^{\lfloor (n-1)/3\rfloor} \lceil \frac{n-3i+1}{2} \rceil$$

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

-- Thu Sep 07, 2017 09:23:46 --

См. также формулы (61)-....

[Yadryara]

Спасибо, maxal. Переобозначение понятно.

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

Стартуя с $q(n,1) = 1$, получаем:

$$q(n,2) = \lfloor \frac{n+1}{2} \rfloor$$

А разве не

$$q(n,2) = \lfloor \frac{n+2}{2} \rfloor\qquad ?$$

Соответственно и дальше, для $q(n,3)$ не согласен.

$$q(n,3) = \left[\frac{(n+3)^2}{12}\right]$$

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

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

Как именно будет зависеть, если нe секрет? У меня младший кэф полинома зависит немного от другого.

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

См. также формулы (61)-....

Благодарю, но пока не нашёл того, что надо.

[maxal]

Проще всего здесь работать через производящии функции.
Понятно, что

$$\sum_{n=1}^{\infty} P(k,n) y^n = [x^k]\ \prod_{i=1}^{\infty} \frac{1}{1-xy^i} = [x^k] \exp\left(\sum_{i=1}^{\infty} \frac{x^iy^i}{(1-y^i)i}\right).$$

Вычислим $k$-й коэффициент кратным дифференцированием, используя формулу формулу Фаа-ди-Бруно:

$$\sum_{n=1}^{\infty} P(k,n) y^n = \frac{1}{k!} B_k\left(0!\frac{y}{1-y},1!\frac{y^2}{1-y^2},2!\frac{y^3}{1-y^3},\dots\right),$$

где $B_k(\dots)$ -- это полный полином Белла.

Вот первый десяток получаемых производящих функций:

k=1: y/(-y + 1)
k=2: -y^2/(-y^3 + y^2 + y - 1)
k=3: -y^3/(y^6 - y^5 - y^4 + y^2 + y - 1)
k=4: y^4/(y^10 - y^9 - y^8 + 2*y^5 - y^2 - y + 1)
k=5: -y^5/(y^15 - y^14 - y^13 + y^10 + y^9 + y^8 - y^7 - y^6 - y^5 + y^2 + y - 1)
k=6: -y^6/(-y^21 + y^20 + y^19 - y^16 - 2*y^14 + y^12 + y^11 + y^10 + y^9 - 2*y^7 - y^5 + y^2 + y - 1)
k=7: -y^7/(y^28 - y^27 - y^26 + y^23 + y^21 + y^20 - y^18 - y^17 - 2*y^16 + 2*y^12 + y^11 + y^10 - y^8 - y^7 - y^5 + y^2 + y - 1)
k=8: y^8/(y^36 - y^35 - y^34 + y^31 + y^29 + y^27 - y^25 - 2*y^24 - y^23 - y^21 + y^20 + y^19 + 2*y^18 + y^17 + y^16 - y^15 - y^13 - 2*y^12 - y^11 + y^9 + y^7 + y^5 - y^2 - y + 1)
k=9: -y^9/(y^45 - y^44 - y^43 + y^40 + y^38 + y^35 - 2*y^33 - y^32 - y^31 - y^30 + y^28 + y^27 + y^26 + 2*y^25 + y^24 + y^23 - y^22 - y^21 - 2*y^20 - y^19 - y^18 - y^17 + y^15 + y^14 + y^13 + 2*y^12 - y^10 - y^7 - y^5 + y^2 + y - 1)
k=10: y^10/(y^55 - y^54 - y^53 + y^50 + y^48 + y^44 - y^43 - y^42 - y^41 - 2*y^40 + y^37 + y^36 + y^35 + y^34 + 3*y^33 - y^30 - y^29 - 2*y^28 - 2*y^27 - y^26 - y^25 + 3*y^22 + y^21 + y^20 + y^19 + y^18 - 2*y^15 - y^14 - y^13 - y^12 + y^11 + y^7 + y^5 - y^2 - y + 1)

Это все рациональные функции, коэффициенты в которых известно как вычислять -- см., например.

-- Thu Sep 07, 2017 13:54:30 --

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

А разве не

Да, я округлил не в ту сторону, но это не суть. Я излагал идею, которая может привести к результату. Но через производящие функции тот же результат можно получить еще проще и быстрее.

[Yadryara]

Спасибо, что вернулись к обозначению $P(k, n)$. Оно пока удобнее.

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

Но через производящие функции тот же результат можно получить еще проще и быстрее.

Возможно. Я ведь делал через интерполяцию не потому, что это единственный метод, а потому, что по-другому не умею.

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

k=7: -y^7/(y^28 - y^27 - y^26 + y^23 + y^21 + y^20 - y^18 - y^17 - 2*y^16 + 2*y^12 + y^11 + y^10 - y^8 - y^7 - y^5 + y^2 + y - 1)

С английским не очень дружу, увы. Можно ли Вас попросить всё-таки довести до конца и написать замкнутую явную формулу, например, для $P(7,n)$. Сравним её с полученной мною.

[maxal]

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

Можно ли Вас попросить всё-таки довести до конца и написать замкнутую явную формулу, например, для $P(7,n)$. Сравним её с полученной мною.

Можно попробовать.

k=7: -y^7/(y^28 - y^27 - y^26 + y^23 + y^21 + y^20 - y^18 - y^17 - 2*y^16 + 2*y^12 + y^11 + y^10 - y^8 - y^7 - y^5 + y^2 + y - 1)

Разлагаем на простейшие дроби:

$${\frac {949}{172800\, \left( y-1 \right) ^{3}}}-{\frac {31}{4608}\,\frac{1}{y+1}}+\frac{1}{972}\,{\frac {10\,y-25}{{y}^{2}+y+1}}+{\frac {1}{1440\, \left( y-1 \right) ^{6}}}-{\frac {1261091}{152409600}\frac{1}{y-1}}$$ $$-{\frac {1}{5040\, \left( y-1 \right) ^{ 7}}}+\frac{1}{49}\,{\frac {{y}^{5}+2\,{y}^{4}+3\,{y}^{3}+4\,{y}^{2}+5\,y+6}{{y}^{6}+{y}^{5}+{y}^{4}+{y}^{3}+{y}^{2}+y+1}}-{\frac {y+2}{162\, \left( {y}^{2}+y+1 \right) ^{2}}}-{\frac {11}{1536\, \left( y+1 \right) ^{2}}}$$ $$-{\frac {1199}{345600\, \left( y -1 \right) ^{2}}}-{\frac {1}{768\, \left( y+1 \right) ^{3}}}-\frac{1}{25}\,{\frac {{y}^{3}+{y}^{2}+2\,y+1}{{y}^{4}+{y}^{3}+{y}^{2}+y+1}}-\frac{1}{32}\,{\frac {y}{{y}^{2}+1}}+\frac{1}{36}\,{\frac {2\,y-1}{{y}^{2}-y+1}}$$ $$-{\frac {1}{2160\, \left( y-1 \right) ^{5}}}-{\frac {1}{480\, \left( y-1 \right) ^{4}}}$$

Извлекаем коэффициент при $y^n$:

$$-(-1)^n{\frac {949}{172800}\binom{-3}{n}}-{\frac {31}{4608}\,(-1)^n}+\frac{1}{972}\,[-25,35,-10]_{n\%3}+(-1)^n{\frac {1}{1440}\binom{-6}{n}}+{\frac {1261091}{152409600}}$$ $$+(-1)^n{\frac {1}{5040}\binom{-7}{n}}+\frac{1}{49}\,[6,-1,-1,-1,-1,-1,-1]_{n\%7} - \frac{1}{162}\,[1,-1,0]_{n\%3}\cdot(n+2)-{\frac {11}{1536}\binom{-2}{n}}$$ $$-(-1)^n{\frac {1199}{345600}\binom{-2}{n} - {\frac {1}{768}\binom{-3}{n}} - \frac{1}{25}\,[1,1,-1,0,-1]_{n\%5} - \frac{1}{32}[0,1,0,-1]_{n\%4} + \frac{1}{36}\,[-1,1,2,1,-1,-2]_{n\%6}$$ $$+(-1)^n{\frac {1}{2160}\binom{-5}{n}} - (-1)^n{\frac {1}{480}\binom{-4}{n}}$$

Здесь $[\dots]_m$ - это извлечение $m$-й компоненты вектора (нумерация начинается с 0).

Как видим формула является полиномом от $n$ при любых фиксированных значениях $n$ по модулям 3, 2^2, 5, 7, причем все модули кроме 2,3 влияют только на свободный член.
Для $n$ кратного 6, с точностью до свободного члена, имеем:

$$-{\frac {949}{172800}\binom{-3}{n}}+{\frac {1}{1440}\binom{-6}{n}}+{\frac {1}{5040}\binom{-7}{n}} - \frac{1}{162}\,(n+2) - {\frac {11}{1536}\binom{-2}{n}}$$ $$-{\frac {1199}{345600}\binom{-2}{n} - {\frac {1}{768}\binom{-3}{n}}+{\frac {1}{2160}\binom{-5}{n}} - {\frac {1}{480}\binom{-4}{n}}$$

$$ = \frac{n^6 + 42n^5 + 560n^4 + 1960n^3 - 11088n^2 - 100800n}{3628800} + C.$$

Возможно, где-то наврал, но не сильно

[ex-math]

Много формул такого сорта можно найти в книге Эндрюса "Теория разбиений".

[Yadryara]

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

Например $P(7, 42)= 3539$, а по Вашей формуле получается $3538.889502...$

ex-math, спасибо. А нет ли там формулы в общем в виде, с заготовки которой я начал стартовый пост?

[maxal]

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

формулы, в том числе и Ваша, всё-таки приближённые

Нет! Описанный мной метод дает точные формулы. Любые несовпадения с ожидаемым -- результат ошибок/опечаток в выкладках.

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

Например $P(7, 42)= 3539$, а по Вашей формуле получается $3538.889502...$

Не знаю по какой формуле вы это считали, но если извлекать прямо из производящей функции - то все ok:

? polcoeff(-y^7/(y^28 - y^27 - y^26 + y^23 + y^21 + y^20 - y^18 - y^17 - 2*y^16 + 2*y^12 + y^11 + y^10 - y^8 - y^7 - y^5 + y^2 + y - 1) + O(y^43), 42)
%1 = 3539

[Yadryara]

Я считал по той, которая у Вас была раньше:

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

$$ = \frac{n^6 + 42n^5 + 560n^4 + 1960n^3 - 11088n^2 - 100800n-110671}{3628800}$$

Сейчас, вижу, Вы исправили $ = \frac{-110671}{3628800}$ на $C$. Но пока не сказано, что такое $C$ и как эту $C$ считать...

[maxal]

Yadryara, чтобы вычислить $C$, нужно к $\frac{-110671}{3628800}$ прибавить все ранее проигнорированные свободные члены в исходной формуле:

$$C = \frac{-110671}{3628800}-{\frac {31}{4608}\,(-1)^n}+\frac{1}{972}\,[-25,35,-10]_{n\%3}+{\frac {1261091}{152409600}}$$ $$ +\frac{1}{49}\,[6,-1,-1,-1,-1,-1,-1]_{n\%7} - \frac{1}{25}\,[1,1,-1,0,-1]_{n\%5} - \frac{1}{32}[0,1,0,-1]_{n\%4} + \frac{1}{36}\,[-1,1,2,1,-1,-2]_{n\%6}.$$

При этом, чтобы получить простое выражение (полином от $n$), нужно зафиксировать значения $n$ по модулям 3,4,5,7. Например, для $n$ кратного $3\cdot 4\cdot 5\cdot 7=420$ получаем:

$$C= \frac{-110671}{3628800}-{\frac {31}{4608}}+\frac{1}{972}\,(-25)+{\frac {1261091}{152409600}} +\frac{1}{49}6 - \frac{1}{25} - \frac{1}{36} = 0.$$

То есть, для $n$ кратных $420$ имеем:

$$P(7,n) = \frac{n^6 + 42n^5 + 560n^4 + 1960n^3 - 11088n^2 - 100800n}{3628800}.$$

[Yadryara]

Ага. Не для слабонервных. Проще законно округлить до ближайшего целого. Но если всё-таки перечислять все значения $C$, то у меня получилось так:

$C = -25/175$ если $n/6 \mod 35 \equiv 1, 5, 6, 10, 11, 15, 16, 20, 25, 26, 30, 31$

$C = -18/175$ если $n/6 \mod 35 \equiv 3, 8, 13, 18, 23, 33$

$C = -11/175$ если $n/6 \mod 35 \equiv 2, 4, 9, 12, 17, 19, 22, 24, 27, 29, 32, 34$

$C = 0$ если $n/6 \mod 35 \equiv 0, 21$

$C = 7/175$ если $n/6 \mod 35 \equiv 28$

$C = 14/175$ если $n/6 \mod 35 \equiv 7, 14$

[ex-math]

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

А нет ли там формулы в общем в виде, с заготовки которой я начал стартовый пост?

Не могу сказать, книги нет на руках, но это своего рода энциклопедия по этой теме, хотя и устаревшая наверно.

[maxal]

ex-math в сообщении #1246060 писал(а):

Много формул такого сорта можно найти в книге Эндрюса "Теория разбиений".

Книга в электронном виде есть тут, например:
http://www.vixri.ru/?p=482

[Yadryara]

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

Раз уж тему перенесли в ПР/Р, спрошу ещё вот о чём.

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

Извлекаем коэффициент при $y^n$:

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