Разбиения числа

[cyb12]

Подскажите, можно ли оценить число способов разбиения натурального числа $n$ в сумму $k$ слагаемых (порядок не учитывается, т.е. $1+1+2$ - это то же самое, что $1+2+1$)?

[paha]

уже учитесь пользоваться интернетом http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0

а там и до $k$ слагаемых можно догуглиться:)

[cyb12]

До википедии я-то дошел, а вот с $k$ слагаемыми проблема...

[paha]

Число разбиений $p_k(n)$ числа $n$ не более чем с $k$
слагаемыми равно числу разбиений числа $n$, в которых нет слагаемых, превосходящих $k$ (транспонирование диаграмм Юнга).

1) Сделайте из производящей функции Эйлера $\prod (1-x^i)^{-1}$ производящую функцию для $p_k(n)$

2) Вычисляйте $p_k(n)-p_{k-1}(n)$

[cyb12]

paha в сообщении #333487 писал(а):

Число разбиений $p_k(n)$ числа $n$ не более чем с $k$
слагаемыми равно числу разбиений числа $n$, в которых нет слагаемых, превосходящих $k$ (транспонирование диаграмм Юнга).

1) Сделайте из производящей функции Эйлера $\prod (1-x^i)^{-1}$ производящую функцию для $p_k(n)$

2) Вычисляйте $p_k(n)-p_{k-1}(n)$

Как сделать 1)?

[paha]

ну, первая же глупая мысль оказывается верной:))

попробуйте руками (умножая эти бесконечные произведения) записать хотябы первые 5 членов произведения Эйлера

[cyb12]

Короче ясно. То, что вы предлагаете, я не в силах сделать, ибо с теорией производящих функций знаком очень мало.
Кто-нибудь знает ответ на мой исходный вопрос?

[ИСН]

Ответ Вам сказали. Простой формулы нет.
(Хотя, это смотря какое k. Если небольшое - 1 там, 2, 3 - то...)

[cyb12]

Да я понимаю, что "простой формулы" нет, если уж даже без ограничений на количество слагаемых асимптотика в теореме Харди-Рамануджана далеко не проста.
Но есть ли где об этом почитать? Или пока я не начну изучать производящие функции, мне этого не понять?

[paha]

производящие функции -- это то, что Вам поможет в работе с любыми задачами такого рода (комбинаторными), регулярный аппарат, так сказать

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

[cyb12]

paha в сообщении #333565 писал(а):

производящие функции -- это то, что Вам поможет в работе с любыми задачами такого рода (комбинаторными), регулярный аппарат, так сказать

Я это уж понял, но почему-то нам их не рассказали , и мне очень хочется их изучить, но пока нет времени.

[cyb12]

paha в сообщении #333487 писал(а):

Число разбиений $p_k(n)$ числа $n$ не более чем с $k$
слагаемыми равно числу разбиений числа $n$, в которых нет слагаемых, превосходящих $k$ (транспонирование диаграмм Юнга).

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

Это что-нибудь дает?

[Xaositect]

Число разбиений $n$ на $k$ слагаемых равно числу разбиений $n-k$ на не более, чем $k$ слагаемых. (док-во: вычитаем по единичке из каждого и, возможно, убираем нули)

[cyb12]

Xaositect в сообщении #334082 писал(а):

Число разбиений $n$ на $k$ слагаемых равно числу разбиений $n-k$ на не более, чем $k$ слагаемых. (док-во: вычитаем по единичке из каждого и, возможно, убираем нули)

Это как раз следует из того, что я сказал?

cyb12 в сообщении #334071 писал(а):

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

То есть одно слагаемое равно $k$ заведомо, потому разбиваем $n-k$ на не более, чем $k$ слагаемых.

[Xaositect]

Да, так тоже можно доказать.