2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Явные формулы для количества разбиений
Сообщение05.09.2017, 16:28 
Аватара пользователя


29/04/13
7128
Богородский
Настоящая тема является продолжением обсуждения вот этой темы. Опубликовано отдельно с учётом пожелания 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$ включительно.

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение07.09.2017, 16:40 
Модератор
Аватара пользователя


11/01/06
5660
В терминах стандартной функции разбиений $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)-....

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение07.09.2017, 21:12 
Аватара пользователя


29/04/13
7128
Богородский
Спасибо, 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)-....

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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение07.09.2017, 21:42 
Модератор
Аватара пользователя


11/01/06
5660
Проще всего здесь работать через производящии функции.
Понятно, что
$$\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 писал(а):
А разве не

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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 06:38 
Аватара пользователя


29/04/13
7128
Богородский
Спасибо, что вернулись к обозначению $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)$. Сравним её с полученной мною.

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 08:24 
Модератор
Аватара пользователя


11/01/06
5660
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.$$
Возможно, где-то наврал, но не сильно :D

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 08:37 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 11:35 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 14:12 
Модератор
Аватара пользователя


11/01/06
5660
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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 15:00 
Аватара пользователя


29/04/13
7128
Богородский
Я считал по той, которая у Вас была раньше:
maxal в сообщении #1246059 писал(а):
$$ = \frac{n^6 + 42n^5 + 560n^4 + 1960n^3 - 11088n^2 - 100800n-110671}{3628800}$$


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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 15:26 
Модератор
Аватара пользователя


11/01/06
5660
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}.$$

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 18:14 
Аватара пользователя


29/04/13
7128
Богородский
Ага. Не для слабонервных. Проще законно округлить до ближайшего целого. Но если всё-таки перечислять все значения $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$

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 19:26 
Заслуженный участник
Аватара пользователя


24/02/12
1842
Москва
Yadryara в сообщении #1246091 писал(а):
А нет ли там формулы в общем в виде, с заготовки которой я начал стартовый пост?
Не могу сказать, книги нет на руках, но это своего рода энциклопедия по этой теме, хотя и устаревшая наверно.

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение08.09.2017, 19:29 
Модератор
Аватара пользователя


11/01/06
5660
ex-math в сообщении #1246060 писал(а):
Много формул такого сорта можно найти в книге Эндрюса "Теория разбиений".

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

 Профиль  
                  
 
 Re: Явные формулы для количества разбиений
Сообщение13.09.2017, 09:22 
Аватара пользователя


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

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

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)$ ?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group