Find the number of permutations $\mathrm{a}_{1}, \mathrm{a}_{2}, \ldots, \mathrm{a}_{10}$ of the numbers $1,2, \ldots, 10$, such that $\mathrm{a}_{\mathrm{i}+1}$ is not less than $\mathrm{a}_{\mathrm{i}}-1$ (for $\mathrm{i}=1,2, \ldots, 9)$.
We can encode the required permutations as follows: each $\mathrm{a}_{\mathrm{i}}, \mathrm{i}=1,2, \ldots, 9$, will be marked with a "+" if $\mathrm{a}_{\mathrm{i}+1}>\mathrm{a}_{\mathrm{i}}$, and with a "-", if $\mathrm{a}_{\mathrm{i}+1}=\mathrm{a}_{\mathrm{i}}-1$. Prove that the permutation is uniquely restored by its "code".

## Solution

After each number in the permutation, which is mentioned in the condition, follows either a larger number or one less. Each $\mathrm{a}_{\mathrm{i}}, \mathrm{i}=1,2, \ldots, 9$, will be marked with a "+" if $\mathrm{a}_{\mathrm{i}+1}>\mathrm{a}_{\mathrm{i}}$, and with a "-", if $\mathrm{a}_{\mathrm{i}+1}=\mathrm{a}_{\mathrm{i}}-1$. Thus, each permutation is associated with a string of 9 symbols "+" and "-". Clearly, the number of such strings is $2^{9}=512$ (for each of the 9 symbols in the string, there are two possibilities - to be a plus or a minus). It remains to show that this correspondence is one-to-one, i.e., the permutation is uniquely restored from the string of pluses and minuses. Indeed, let at the beginning of the string there are $\mathrm{n}_{1}$ minuses (possibly, $\mathrm{n}_{1}=0$), and then a plus, then $\mathrm{n}_{2}$ minuses, then a plus, and so on. Then the permutation must start with a group of $\mathrm{n}_{1}+1$ numbers in a row in descending order, followed by a new group of $\mathrm{n}_{2}+1$ numbers in a row in descending order, and so on. At the same time, the first number of the second group must be greater than the last number of the first group. Since the first and second groups contain different numbers, this means that each number of the second group is greater than each number of the first group. Similarly, each number of the third group is greater than each number of the second group, and so on. The above reasoning allows us to uniquely restore the permutation (while using the fact that each of the numbers $1,2, \ldots, 10$ must appear in the permutation); the permutation has the form: $\mathrm{n}_{1}+1, \mathrm{n}_{1}, \ldots, 1, \mathrm{n}_{1}+\mathrm{n}_{2}+2, \mathrm{n}_{1}+\mathrm{n}_{2}+1, \ldots, \mathrm{n}_{1}+2, \ldots$ (The numbers in the permutation are arranged in "steps" of lengths $\mathrm{n}_{1}+1, \mathrm{n}_{2}+1, \ldots$ of consecutive numbers in descending order.)

## Answer

$2^{9}=512$.