Разбиение числа [Комбинаторика]

[Whitaker]

Здравствуйте уважаемые!
Несколько дней назад мне попалась задачка из Виленкина "Комбинаторика". Она из раздела "Точечные Диаграммы". Сформулирую ее:
Доказать, что число способов разбить $n$ на слагаемые так, чтобы ни одно число не входило в сумму более $r-1$ раз, равно числу способов разбить $n$ на части, не делящиеся на $r$.

Вот моя попытка решения: Точечная диаграмма, изображающая разбиение числа $n$ на слагаемые так, чтобы ни одно число не входило в сумму более $r-1$ раз состоит из $n$ точек и пусть для удобства она имеет следующий вид.

По условию все $n_i \leq r-1$.
Изобразим теперь двойственную диаграмму, которая получена из исходной поворотом на 90 градусов.

Очевидно, что несколько первых слагаемых двойственной диаграммы не делятся на $r$ так как $n_k<r$
Пусть теперь некоторое $k$-е слагаемое двойственной диаграммы делится на $r$, тогда отмечаем его последнюю точку и перемещаем его на самый верх диаграммы и этим преобразванием мы получаем, что $k$-е слагаемое не делится уже на $r$. Таким образом, каждому разбиению числа $n$ на слагаемые, так чтобы ни одно число не входило в сумму более $r-1$ раз можно сопоставить разбиение числа $n$ на слагаемые не делящиеся на $r$.

Обратно, если задано разбиение числа $n$ на слагаемые не делящиеся на $r$, то каждое слагаемое имеет вид $rm_k+l$, где $ 1\leq l \leq r-1$, то выделяя в нем первые $rm_k$ точек помещаем их вверх по одной точке, т.е. получаем стоблец из $rm_k$ точек. Если $m_k=0$, то оставляем без изменения.

Не судите строго. Честно говоря, я не знаю является ли это правильным решением, но я проиллюстрировал свою попытку. Над этой задачкой я думаю уже 4-й день и в голову пришла только такая идея и больше ничего. Буду рад услашть Ваши замечания.

С уважением, Whitaker.

[Whitaker]

Буду признателен, если кто-нибудь что-нибудь скажёт насчёт моей попытки решения

[PAV]

Особо не вникал в предложенное решение, однако такое ощущение, что там не уделено достаточное внимание обоснованию того, почему предложенные преобразования диаграммы будут обратимы. То есть нужно обосновать, что мы сможем сделать обратный шаг, глядя только на полученную в его результате диаграмму.

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

Пусть есть разбиение на слагаемые, каждое из которых не делится на $r$, однако может встречаться произвольное количество раз. Если некоторое слагаемое $s$ встречается $k\ge r$ раз, тогда делим $k$ на $r$ с остатком: $k=ar+b$ и заменяем $ar$ слагаемых $s$ на $a$ слагаемых $s'=rs$. Теперь слагаемое $s$ встречается в сумме $b<r$ раз (возможно, ноль раз). Важно заметить, что новые добавленные слагаемые в сумму все делятся на $r$, поэтому они не могут "испортить" те слагаемые, которые были до этого (сделать их количество большим, чем $r$).

Теперь все слагаемые, которые на $r$ не делятся, присутствуют в правильном количестве, и мы их больше трогать не будем. Смотрим на новые добавленные слагаемые, кратные $r$. Важно заметить, что все они делятся на $r$ в первой степени, и ни одно из них не делится на $r^2$. С ними поступаем аналогичным образом: если некоторые из них встречаются больше раз, чем требуется, то аналогичным образом мы уменьшим их количество, добавив новые слагаемые, каждое из которых будет уже делиться на $r^2$, но не на $r^3$. И так до тех пор, пока процесс не закончится. Поскольку на каждом шаге число слагаемых уменьшается, то процесс обязательно закончится.

Нетрудно понять, что эта процедура обратима. Имея разложение на слагаемые, каждое из которых встречается не чаще, чем $r-1$ раз, нужно определить максимальную степень $r$, на которую делятся некоторые из этих слагаемых, и обратно их разделять от старших степеней к младшим.

[Whitaker]

Гениальное решение PAV
Благодарю Вас за столь подробный и чёткий ответ