2014 dxdy logo

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

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


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


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

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

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

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

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



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


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

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


29/04/13
7125
Богородский
Покорно благодарю. Слишком сложным, всё же, получается полином в общем виде. Если $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!}$$

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


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

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


29/04/13
7125
Богородский
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$.

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


29/04/13
7125
Богородский
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$$

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

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


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

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

Для $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$.

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


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

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


11/01/06
5660
Yadryara в сообщении #1247856 писал(а):
Степень соответствующих внутренних полиномов увеличивается на $3$, имеется строгая знакопеременность их коэффициентов, а также обнуление их суммы:

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

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


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

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


05/09/16
11461
Ну, чтоб не пропало, оставлю тут.

Подсчеты на 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, то получаем сами эти разбиения в виде набора одномерных массивов (векторов) чисел-слагаемых.

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


29/04/13
7125
Богородский
Возвращался к явным формулам при обсчёте подзадач из темы «Сложная числовая задача (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}$$

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

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

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



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

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


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

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