Докажите, что число разбиений натурального числа n в сумму ровно k натуральных слагаемых равно числу разбиений n в сумму нескольких натуральных слагаемых, в которых наибольшее слагаемое равно k.

Для доказательства этого утверждения мы воспользуемся методом диаграмм Ферре (или графическим представлением разбиений).

1. Определение

Пусть $P(n, k)$ — количество разбиений числа $n$ на ровно $k$ натуральных слагаемых. Пусть $Q(n, k)$ — количество разбиений числа $n$, в которых наибольшее слагаемое равно $k$.

Нам нужно доказать, что $P(n, k) = Q(n, k)$.

2. Решение через диаграммы Ферре

Диаграмма Ферре — это способ представления разбиения числа $n = \lambda_1 + \lambda_2 + \dots + \lambda_m$ (где $\lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_m > 0$) в виде сетки из точек (или...