Count the number of permutations

Probability Level 3

Among $5!$ permutations of the digits $1, 2, 3, 4, 5$ consider those permutations $\overline{a_1 a_2 a_3 a_4 a_5}$ that there is no triple of indices $i < j < k$ such that $a_k < a_i < a_j$ . In other words, $a_i$ , $a_j$ and $a_k$ are not in the same relative positions as $2$ , $3$ and $1$ .

For example, $32154$ is an example of such permutation whereas $53412$ is not (since $a_4 = 1 < a_2 = 3 < a_3 = 4$ ).

How many permutations are there?

The answer is 42.

1 solution

Patrick Corn
Jul 20, 2018

Let $a_n$ be the number of such permutations on $n$ digits. Look at where $n$ is in the list. The digits to the left of $n$ must all be less than the digits to the right of $n.$ So the digits to the left of $n$ form a permutation of $1,2,\ldots,k$ and the digits to the right form a permutation of $k+1,\ldots,n-1.$ And the full permutation satisfies the condition if and only if the two sub-permutations on the left and right satisfy the condition.

If we set $a_0 = 1,$ this leads to the formula $a_n = \sum_{k=0}^{n-1} a_k a_{n-1-k}.$

This is the same recurrence relation satisfied by the Catalan numbers , with the same initial condition $a_0=1.$ So $a_n$ is the $n$ th Catalan number, $a_n = \frac1{n+1} \binom{2n}{n}.$ In particular, $a_5 = \fbox{42}.$

Count the number of permutations

The answer is 42.

1 solution

0 pending reports