Ответ на пропавший вопрос

[VAL]

Нашел ответ на вопрос о количестве композиций (упорядоченных разбиений числа) с ограничением на размер слагаемых. Но пока искал, вопрос куда-то пропал...
Ау!

[ИСН]

Да, я тоже видел. Хотел ещё спросить, что такое композиции, да подумал, что и так прочитаю в ответе.

[Sonic86]

Это?
topic45193.html

[VAL]

Sonic86 в сообщении #464431 писал(а):

Это?
topic45193.html

Нет.
Там требовалось найти количество представлений числа $n$ в виде упорядоченных сумм слагаемых, не превосходящих $k$.
Ответ получается такой:
При $k\ge n \ $ имеем $r(n,k)=2^{n-1}$, при $k=n-1 \ $ имеем $r(n,k)=2^{n-1}-1$, для остальных $k \ $ получается $r(n,k)=\sum_{i=1}^k r(n,n-i)$.
В частности, при $k=2$ получаются числа Фибоначчи.