Да, ещё — к рекуррентной формуле для p(n) можно прийти и "лобовым" подходом (via). А именно, давайте опять посмотрим на более подробную информацию, но на этот раз ограничим не наибольшее слагаемое, а зафиксируем наименьшее: пусть p(n,j) это число разбиений n с наименьшим слагаемым, равным j.

Тогда:
p(n)=p(n+1,1) — потому что можно к любому разбиению дописать 1; иными словами,
p(n,1)=p(n-1).

p(n)=\sum_{j=1}^n p(n,j) — потому что последнее слагаемое должно быть хоть каким-нибудь.

А дальше можно делать индукцию "уменьшением j":
p(n,j) = p(n-1,j-1) - p(n-j,j-1),
первое — это если мы на 1 уменьшили наименьшее слагаемое j, а второе — это лишние слагаемые, которые мы при этом посчитали (предыдущее слагаемое это тоже (j-1), а не хотя бы j, так что 1 обратно к последнему добавить нельзя).