
5. The numbers 1 to 12 are arranged in a sequence. The number of ways this can be done equals $12 \times 11 \times 10 \times \cdots \times 1$. We impose the condition that in the sequence there should be exactly one number that is smaller than the number directly preceding it.

How many of the $12 \times 11 \times 10 \times \cdots \times 1$ sequences meet this demand?



5. A sequence meeting the demand is called 'good'. We will determine the number of good sequences in an indirect way, by first counting something else.

First consider the number of ways in which we can colour the numbers 1 to 12 , each number being coloured either red or blue. As there are two options (red or blue) for each of the 12 numbers independently, there are $2^{12}$ possible colourings. We call a colouring 'good' if there is at least one number of each colour, and the largest red number is larger than the smallest blue number. There are exactly 13 colourings that are not good: the colouring having only blue numbers, and the twelve colourings in which the red numbers are precisely the numbers 1 to $k$, for some $k=1,2, \ldots, 12$ (in the case $k=12$, there are no blue numbers.) In total, there are $2^{12}-13=4083$ good colourings.

We will now show that the number of good sequences is equal to the number of good colourings, by perfectly matching colourings and sequences. Take a good sequence and suppose that $a$ is the number smaller than its immediate predecessor in the sequence. To this sequence we associate the following colouring: the numbers preceding $a$ in the sequence are coloured red, and the other numbers are coloured blue. This will be a good colouring.

As an example, consider the good sequence $1,3,4,5,8,9,2,6,7,10,11,12$. Hence, $a=2$. The numbers $1,3,4,5,8$, and 9 will be coloured red, the numbers $2,6,7,10,11$, and 12 will be blue. This is a good colouring, because $9>2$.

In this way, each good colouring is obtained precisely once from a good sequence. Indeed, for a given good colouring, we can find the unique corresponding good sequence as follows: write down the red numbers in increasing order, followed by the blue numbers in increasing order.

We conclude that there are 4083 sequences meeting the demand.

