Разбиения положительного числа на положительные слагаемые

[arseniiv]

(В духе темы topic5893.html.)

Интересно, сколько их для данного числа $n$. Вроде бы этому соответствовали какие-то известные числа, но забыл. Не подскажете?

Установил, что если порядок слагаемых играет роль, получается ровно $2^{n-1}$ cпособов, биекцией с двоичными числами из $n$ цифр. Нижняя естественная оценка — $n$ — число сумм с $n-k$ единицами и числом $k$.

[gris]

Надеюсь, само число и слагаемые натуральные?

Недавно обсуждалось http://dxdy.ru/post221418.html

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

[arseniiv]

Спасибо!

[ewert]

arseniiv в сообщении #340207 писал(а):

Установил, что если порядок слагаемых играет роль, получается ровно $2^{n-1}$ cпособов,

Нет, вот этого точно не получается. Если, конечно, не различать комбинации типа 2+3+1+5 и 2+3+1+5, но различать 2+3+1+5 и 2+5+1+3. Тогда получается просто $C_{n-1}^{k-1}$.

[arseniiv]

Почему?? Скорее всего, мы друг друга не поняли (я вас точно). Смотрите:

1. 10000  ~  5 
2. 10001  ~  4 + 1 
3. 10010  ~  3 + 2 
4. 10011  ~  3 + 1 + 1 
5. 10100  ~  2 + 3 
6. 10101  ~  2 + 2 + 1 
7. 10110  ~  2 + 1 + 2 
8. 10111  ~  2 + 1 + 1 + 1 
9. 11000  ~  1 + 4 
10. 11001  ~  1 + 3 + 1 
11. 11010  ~  1 + 2 + 2 
12. 11011  ~  1 + 2 + 1 + 1 
13. 11100  ~  1 + 1 + 3 
14. 11101  ~  1 + 1 + 2 + 1 
15. 11110  ~  1 + 1 + 1 + 2 
16. 11111  ~  1 + 1 + 1 + 1 + 1 

[Профессор Снэйп]

arseniiv в сообщении #340207 писал(а):

Установил, что если порядок слагаемых играет роль, получается ровно $2^{n-1}$ cпособов...

Ага. Между $n$ шарами расставляем $n-1$ перегородку и затем выделяем произвольное множество перегородок.

Если же порядок слагаемых не играет роли, то тогда сложнее

[Legioner93]

arseniiv в сообщении #340207 писал(а):

Вроде бы этому соответствовали какие-то известные числа

Вот эти вроде http://oeis.org/classic/A000041