Bulgaria competition problems, 2022

We will derive a closed formula for the good permutations of the numbers from 1 to $n$. Consider a good permutation $\sigma$, where $j = \sigma^{-1}(1)$ is an arbitrary index inbetween 1 and $n$. Then, the first $j-1$ positions of $\sigma$ contain the numbers $2, 3, \ldots, j$, forming a good permutation of $j-1$ elements, while the last $n-j$ positions of $\sigma$ contain the numbers $j+1, \ldots, n$, forming a good permutation of $n-j$ elements. It is an easy exercise to check that the above condition is not only necessary but also sufficient for the construction of an arbitrary good permutation of $n$ elements. Hence, denoting by $S_n$ the corresponding number of good permutations, we derive that $(S_n)_{n \ge 0}$ satisfies $S_0 = 1$ and $S_n = \sum_{j=0}^{n-1} S_j S_{n-1-j}$, $\forall n \ge 1$. Therefore, $S_n = \frac{1}{n+1} \binom{2n}{n}$ is the $n$-th Catalan number. In particular,

$$S_{10} = \frac{1}{11} \binom{20}{10} = \frac{12 \cdot 13 \cdots 20}{2 \cdot 3 \cdots 10} = 4 \cdot 13 \cdot 17 \cdot 19 = 16796.$$