Задача М40‍‍

Задача состояла из двух заданий, причём первое было намного легче второго, долускало несколько различных решений. Приведём одно из них, достаточно интересное и поучительное, следуя рассуждениям И. Алексеева из г. Новомосковска Тульской обл. и А. Аляева из Пачелмы Пензенской обл. Прежде проверим, что $$ 1\cdot2+2\cdot3+3\cdot4+\ldots+n(n+1)=\dfrac{n(n+1)(n+2)}3.\tag1 $$ Действительно, $$ \begin{align*} 1\cdot2&=\dfrac{1\cdot2\cdot3}3,\\ 2\cdot3&=\dfrac{2\cdot3\cdot4}3-\dfrac{1\cdot2\cdot3}3,\\ 3\cdot4&=\dfrac{3\cdot4\cdot5}3-\dfrac{2\cdot3\cdot4}3,\\ n\cdot(n+1)&=\dfrac{n\cdot(n+1)\cdot(n+2)}3-\dfrac{(n-1)\cdot n\cdot(n+1)}3. \end{align*} $$ Отсюда и следует справедливость равенства (1).

Распишем теперь заданную сумму в виде треугольной таблицы $$ \colsep{3pt}{\begin{array}{cccccccccc} 1\\ 1&2\\ 1&2&3\\ 1&2&3&4\\ 1&2&3&4&5\\ 1&2&3&4&5&6\\ 1&2&3&4&5&6&7\\ &&&\mathclap{{\ldots}\,{\ldots}\,{\ldots}}\\ 1&2&3&4&5&6&7&\ldots&n-1\\ 1&2&3&4&5&6&7&\ldots&n-1&n \end{array}} $$

Находить значение этой суммы можно не только отысканием суммы столбцов и дальнейшим их сложением. Можно, напротив, отыскивать суммы по строкам таблицы. Поскольку $$ 1+2+3+\ldots+k=\dfrac{k(k+1)}2, $$ мы придём к сумме, записанной в левой части равенства (1). Поэтому получим $$ n\cdot1+(n-1)\cdot2+\ldots+1\cdot n=\dfrac{1\cdot2}2+\dfrac{2\cdot3}2+\ldots+ \dfrac{n(n+1)}2=\dfrac{n(n+1)(n+2)}6. $$

Более общую сумму, приведённую в условии задачи, можно отыскать с помощью комбинаторных соображений.

Напомним формулу для $C_n^k$‍‍ — числа сочетаний из $n$‍‍ элементов по $k$‍‍‍: $$ C_n^k=\dfrac{n(n-1)(n-2)\cdot\ldots\cdot(n-k+1)}{1\cdot2\cdot\ldots\cdot k}= \dfrac{n(n-1)(n-2)\cdot\ldots\cdot(n-k+1)}{k!}. $$

Очевидно равенство $$ \begin{align*} [1\cdot2\cdot\ldots\cdot k]&\cdot[n\cdot(n-1)\cdot\ldots\cdot(n-k+1)]+{}\\ [2\cdot3\cdot\ldots\cdot(k+1)]&\cdot[(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k)]+ \ldots+{}\\ {}+[(n-k+1)\cdot(n-k+2)\cdot\ldots\cdot n]&\cdot[k\cdot(k-1)\cdot\ldots\cdot1]=\\ &=(k!)^2(C_k^k\cdot C_n^k+C_{k+1}^k\cdot C_{n-1}^k+C_{k+2}^k\cdot C_{n-2}^k+ \ldots+C_n^k\cdot C_k^k). \end{align*} $$

Каждое слагаемое вида $C_{k+m}^k\cdot C_{n-m}^k$‍‍ (где $m=0$‍,‍ 1, 2, $\ldots$‍,‍ $n-k$‍),‍ представляет число сочетаний (или выборок) по $2k$‍‍ элементов из $n+k$‍,‍ но не всех возможных, а таких, образуя которые сперва выбирают $k$‍‍ элементов из числа определённых $k+m$‍‍ элементов, а затем ещё $k$‍‍ элементов из оставшихся $n-m$‍.‍ Сказанное можно наглядно пояснить так. Разместим «в строчку» данные $n+k$‍‍ элементов и проведём вертикальную черту, отделяющую $k+m$‍‍ элементов слева от $n-m$‍‍ элементов справа. Выберем каким-то образом $k$‍‍ элементов слева от черты и $k$‍‍ элементов справа от черты, а затем образуем соединение каждой из таких «левых» выборок с каждой из таких «правых» выборок. Всего таких соединений будет, очевидно, $C_{k+m}^k\cdot C_{n-m}^k$‍.‍

Теперь нетрудно доказать, что $$ C_k^k\cdot C_n^k+C_{k+1}^k\cdot C_{n-1}^k+C_{k+2}^k\cdot C_{n-2}^k+\ldots+ C_n^k\cdot C_k^k=C_{n+k+1}^{2k+1}.\tag2 $$ Для этого достаточно установить взаимно однозначное соответствие между выборками из $n+k+1$‍‍ элементов по $2k+1$‍‍ и выборками из $n+k$‍‍ элементов такого вида: «$k$‍‍ элементов слева от черты; черта; $k$‍‍ элементов справа от черты», общее количество которых равно сумме, стоящей в левой части равенства (2). Итак, искомая сумма равна $$ (k!)^2\cdot C_{n+k+1}^{2k+1}=\dfrac{(n+k+1)!\,(k!)^2}{(2k+1)!\,(n-k)!}. $$

В частности, для первого задания М40 имеем $k=1$‍‍ и поэтому сумма составит $C_{n+2}^3=\dfrac{(n+2)(n+1)n}6$‍.‍ Если приведённый путь рассуждений покажется вам трудным и тем более если он покажется вам интересным, рекомендуем заглянуть в книгу Н. Я. Виленкина «Комбинаторика» (М., «Наука», 1969). Там, в частности, на стр. 57 доказана формула (24), аналогичная формуле (2).