a) Представим себе, что все жители города выстроены в несколько шеренг, причём в $m$-й шеренге стоят все жители $m$-го по численности дома, и шеренги выравнены по левому флангу (на рисунке люди изображены точками). Таким образом, $c_m$ — это число людей в $m$-й шеренге. Заметим теперь, что число людей в $k$-й колонне равно $d_k$. В самом деле, в $k$-й колонне стоит по одному человеку из каждой шеренги, содержащей не менее $k$ человек; по условию, число таких шеренг равно $d_k$. Например, на рисунке изображён случай, когда
$$\begin{gather*}
c_1=5, \quad c_2=c_3=3, \quad c_4=1,\\
d_1=4, \quad d_2=d_3=3, \quad d_4=d_5=1.
\end{gather*}$$
Из сказанного сразу следует, что каждая из сумм $c_1+c_2+\ldots+c_m+\ldots$ и $d_1+d_2+\ldots+d_k+\ldots$ есть общее число жителей города: первый раз мы пересчитали их, сгруппировав в шеренги, а второй раз — в колонны. Это доказывает утверждение а).
Рисунок
б) Дадим левофланговым во всех шеренгах по одному флажку, следующим за ними людям — по 3 флажка и т. д., так что все люди в $k$-й колонне получат по $2k-1$ флажков. Сосчитаем двумя способами общее количество розданных флажков. Так как каждый из $d_k$ человек в $k$-й колонне получил $2k-1$ флажков, общее число флажков равно $d_1+3d_2+5d_3+\ldots$. С другой стороны, люди из $m$-й шеренги получили $1+3+\ldots+(2c_m-1)=c_m^2$ флажков, так что общее число флажков равно $c_1^2+c_2^2+\ldots+c_m^2+\ldots$ Приравнивая эти выражения, получаем первое равенство пункта б).
Второе равенство можно доказать аналогично, но проще приказать всем собравшимся жителям повернуться на $90^\circ$. При этом шеренги превратятся в колонны, а колонны в шеренги, так что теперь $c_m$ — это количество людей в $m$-й колонне, а $d_k$ — в $k$-й шеренге. Записывая для нового построения уже доказанное равенство, получим требуемое.
Массивы точек, подобные изображённому на рисунке, называются диаграммами Юнга. Они играют важную роль в современной комбинаторике и находят интересные применения в программировании. Об этом можно прочитать в третьем томе замечательной книги Д. Кнута «Искусство программирования для ЭВМ» (М., «Мир», 1978).
