Разбиение числа на слагаемые

[druggist]

Существует ли общее выражение для числа неориентированных наборов слагаемых на которое можно разбить произвольное натуральное число $M$ и каковы доли различных слагаемых меньших $M$ во всех таких наборах. Поясню, пусть $M=5$, тогда $5=$

$5$
$1+4=2+3$ (наборы неориентированные, так что имеем всего два варианта разбиения на 2 части)
$1+1+3=2+2+1$
$1+1+1+2$
$1+1+1+1+1$
Число различных разбиений равно $1+2+2+1+1=7$, обозначим $P(m)$ число различных слагаемых m от 1 до M:
$P(1)=12$
$P(2)=4$
$P(3)=2$
$P(4)=1$
$P(5)=1$
Какова будет зависимость $P(m)$ для больших $M$?

[ИСН]

druggist в сообщении #649676 писал(а):

для числа неориентированных наборов слагаемых на которое можно разбить произвольное натуральное число $M$

A000041
А дальше надо смотреть.

-- Пн, 2012-11-26, 00:23 --

Вот, уже нашёл:
A000070
довольно простым образом связанная с предыдущей (которая, однако, сама непроста) - является

Цитата:

...also the number of 1's in all partitions of n

сиречь Ваше $P(1).$
Может, и все остальные где-нибудь найдутся?

[druggist]

Я не совсем понял, тут последовательность n начинается с нуля, т.е., $a(0)=1, a(1)=1, a(3)=2$ и т.д.?

Цитата:

a(n) = number of partitions of n (the partition numbers).

Цитата:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101,

[ИСН]

$a(3)=3$, а в остальном верно - да, с нуля.

[ex-math]

Общее выражение для $p(n)$ -- так обозначают число разбиений $n$ -- существует и называется формулой Радемахера. Это абсолютно сходящийся ряд, довольно удобный для вычислений, так как если хвост его будет меньше $\frac12$, дальше можно не суммировать, ведь $p(n)$ -- натуральное. Если интересен главный член асимптотики, то

$$ p(n)\sim\frac{e^{\pi\sqrt{\frac{2n}3}}}{4n\sqrt 3}. $$

По второму вопросу посмотрите книжку Эндрюса "Теория разбиений" -- там много такого, может и найдется что.