Problem 858

## First Solution.

The solution is $3^{n-1}-2^{n-1}$.

1 point

For each $k=2,3, \ldots, n$, we will consider the case where the player with number $k$ on their jersey is sold at the end of the season. We will calculate the number of possible jersey distributions for the remaining players in this case, and then sum the results over all $k$.

Fix (the sold) player with number $k$. The player with number 2 can get number 1 or 2 in the new season. The player with number 3 can get number 1, 2, or 3 in the new season, but cannot get the same number as the player with number 2, so there are only two possibilities. The player with number $i$ ($i=2, \ldots, k-1$) can be assigned one of the first $i$ numbers in the new season, but it cannot be the same number as any of their $i-2$ predecessors, so there are $i-(i-2)=2$ ways to choose.

There are a total of $k-2$ such players, so the number of ways to assign jerseys for the new season to players who had numbers $2,3, \ldots, k-1$ this season is $2^{k-2}$.

The player with number $k+1$ can be assigned one of the first $k+1$ numbers in the new season, but it cannot be the same number as any of the first $k-2$ players, which means there are exactly three possibilities. The player with number $j$ ($j=k+1, \ldots, n$) can be assigned one of the first $j$ numbers in the new season, but it cannot be the same number as any of their $j-3$ predecessors, so there are $j-(j-3)=3$ ways to choose.

There are a total of $n-k$ such players, so the number of ways to assign jerseys for the new season to players who had numbers $k+1, k+2, \ldots, n$ this season is $3^{n-k}$.

Therefore, the total number of ways to distribute jerseys to the remaining players in the case where the player with number $k$ is sold is $2^{k-1} \cdot 3^{n-k}$.

When we sum all the possibilities (depending on the sold player with number $k$), the total number of ways to assign numbers to the players for the new season is

$$2^{0} \cdot 3^{n-2}+2^{1} \cdot 3^{n-3}+\cdots+2^{n-2} \cdot 3^{0}$$

Using the identity for the difference of equal powers of two numbers, the above sum can also be written as

$$2^{0} \cdot 3^{n-2}+2^{1} \cdot 3^{n-3}+\cdots+2^{n-2} \cdot 3^{0}=\frac{3^{n-1}-2^{n-1}}{3-2}=3^{n-1}-2^{n-1}$$

which gives us the final result.