Task 2. Let $n>1$ be an integer. In a row, there are $n$ boxes, and we have $n+1$ identical stones. A distribution is a way to distribute the stones over the boxes, with each stone being in exactly one box. We say that two such distributions are one stone's throw apart if we can obtain one distribution from the other by moving exactly one stone to a different box. The sociability of a distribution $a$ is defined as the number of distributions that are one stone's throw apart from $a$. Determine the average sociability over all possible distributions.

(Two distributions are the same if the $i$-th box in both rows contains the same number of stones, for all $i \in\{1,2, \ldots, n\}$.)

Answer. $\frac{n^{2}-1}{2}$

In the solutions below, we call two distributions neighbors if they are one stone's throw apart.
Solution I. We count the number, $N_{k}$, of distributions that contain exactly $k$ empty boxes with $0 \leq k \leq n-1$ (since not all boxes can be empty). There are $\left(\begin{array}{l}n \\ k\end{array}\right)$ ways to choose the empty boxes and by the stars and bars principle $\left(\begin{array}{c}(k+1)+(n-k)-1 \\ k+1\end{array}\right)=\left(\begin{array}{c}n \\ k+1\end{array}\right)$ ways to fill the remaining $n-k$ boxes with $n+1=(n-k)+(k+1)$ stones such that each of these boxes contains at least one stone. This gives a total of $N_{k}=\left(\begin{array}{l}n \\ k\end{array}\right) \cdot\left(\begin{array}{c}n \\ k+1\end{array}\right)$ distributions with exactly $k$ empty boxes.

Given such a distribution, we can move a stone from one of the $n-k$ non-empty boxes to one of the other $n-1$ boxes. This means that there are $(n-k)(n-1)$ different distributions that are one stone move away. Thus, the sociability of each of these $N_{k}$ distributions is $(n-k)(n-1)$.

For $k^{\prime}=(n-1)-k$, the number of distributions with exactly $k^{\prime}$ empty boxes is $N_{k^{\prime}}=\left(\begin{array}{c}n \\ k^{\prime}\end{array}\right) \cdot\left(\begin{array}{c}n \\ k^{\prime}+1\end{array}\right)=\left(\begin{array}{c}n \\ n-1-k\end{array}\right) \cdot\left(\begin{array}{c}n \\ n-k\end{array}\right)=\left(\begin{array}{c}n \\ k+1\end{array}\right) \cdot\left(\begin{array}{l}n \\ k\end{array}\right)$, so $N_{k^{\prime}}=N_{k}$. The sociability of these $N_{k}$ distributions is $\left(n-k^{\prime}\right)(n-1)=(k+1)(n-1)$. Therefore, the average sociability of these two (possibly the same) sets of distributions is $\frac{(n-k)+(k+1)}{2}(n-1)=\frac{n+1}{2}(n-1)$. Since this is constant in $k$, this is also the overall average.