Berezin V.N.

Find the sums

a) $1 \cdot n+2(n-1)+3(n-2)+\ldots+n \cdot 1$.
b) $S_{n, k}=(1 \cdot 2 \cdot \ldots \cdot k) \cdot(n(n-1) \ldots(n-k+1))+(2 \cdot 3 \cdot \ldots \cdot(k+1)) \cdot((n-1)(n-2) \ldots(n-k))+\ldots+((n-k+1)(n-k+$

2)... $\cdot n) \cdot(k(k-1) \cdot \ldots \cdot 1)$
a) First, let's find the sum of the form $1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \ldots + (n-1) n$.

Notice that $3 k(k+1) = k(k+1)(k+2) - (k-1) k(k+1)$. Adding these equalities for $k$ from 1 to $n-1$, we get:

$3(1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \ldots + (n-1) n) = (n-1) n(n+1)$.

Let's return to solving the problem.

$$
1 \cdot n + 2(n-1) + 3(n-2) + \ldots + n \cdot 1 = (n \cdot n - (n-1) n) + (n(n-1) - (n-2)(n-1)) + (n(n-2) - (n-3)(n-2)) + \ldots +
$$

$n \cdot 1 = $

$$
= n \cdot \frac{n(n+1)}{2} - \frac{(n-1) n(n+1)}{3} = \frac{n(n+1)(n+2)}{6}
$$

b) Notice that $(k!)^2 \cdot \left(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}\right)$.

Arrange $n+k$ balls in a row. Each term of the form $C_{k+m}^{k} \cdot C_{n-m}^{k}$ represents the number of ways to choose $2k$ balls from this row, but not all possible ways, only those where $k$ balls are chosen from the first $k+m$ balls, and then another $k$ balls are chosen from the remaining $n-m$ balls.

Summing such terms for $m$ from 0 to $n-k$ can be interpreted as follows: first, insert a partition in the row of balls such that there are at least $k$ balls on each side of the partition, and then choose $k$ balls from the left and $k$ balls from the right of the partition.

Alternatively, we can do the following: take a row of $n+k+1$ balls and choose $2k+1$ of them; then replace the middle of the chosen balls with a partition.

From this, it is clear that $\left(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}\right) = C_{n+k+1}^{2k+1}$, and therefore, $S_{n, k} = (k!)^2 \cdot C_{n+k+1}^{2k+1}$.

## Answer

a) $\frac{n(n+1)(n+2)}{6}$
b) $(k!)^2 \cdot C_{n+k+1}^{2k+1}$