
Problem 3. Let $n>1$ be an integer. Find the number of the permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the numbers $1,2, \ldots, n$ with the following property: there exists only one index $i \in\{1,2, \ldots, n-$ 1\} such that $a_{i}>a_{i+1}$.


Solution. Denote by $p_{n}$ the number of the permutations with the given properties. Obviously, $p_{1}=0$ and $p_{2}=1$. Let $n \geq 2$. The number of the permutations with $a_{n}=n$ is equal to $p_{n-1}$. Consider all the permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ with $a_{i}=n$, where $1 \leq i \leq n-1$ is fixed. Their number is $\binom{n-1}{i-1}$. Consequently

$$
p_{n}=p_{n-1}+\sum_{i=1}^{n-1}\binom{n-1}{i-1}=p_{n-1}+2^{n-1}-1
$$

From here

$$
\begin{aligned}
p_{n} & =\left(2^{n-1}-1\right)+\left(2^{n-2}-1\right)+\cdots+(2-1) \\
& =2^{n}-n-1
\end{aligned}
$$
