Number of permutations $(p_1,\dots,p_6)$ of $\{1,\dots,6\}$ such that for any $1\le k\le5,(p_1,\dots,p_k)$ is not a permutation of $\{1,\dots,k\}$

Question

Problem (INMO 1992 problem #4)

Find the number of permutations $(p_1,p_2,p_3,p_4,p_5,p_6)$ of $\{1,2,3,4,5,6\}$ such that for any $k$ such that $1 \le k \le 5,$ $(p_1,…,p_k)$ does not form a permutation of $\{1,2,….k\}$

My attempt

I have done a very ugly approach i.e doing case work and counting each case separately. After a long time after going through many mistakes,over countings, i have reached the correct answer $461$.

Initially, i have tried to come up with a recursive relation but i ended up missing too many cases.

Question

Since this an olympiad there must be a nicer and elegant solution. Can anybody share their insights to this problem? Thank you.

Answer 1

These are indecomposable permutations. If $f(n)$ is the number of indecomposable permutations of $[n]=\{1,2,\ldots, n\}$ then recurrence relation $$n!=\sum_{i=1}^{n}{f(i)(n-i)!}$$ holds. This can be proven by double counting the number of permutations of $[n].$ The left side is the standard formula. The right side does casework on the leftmost index $i$ at which the first $i$ numbers in a permutation of $[n]$ forms the set $[i].$ We get $f(i)$ from the fact that for all lower indices $j<i,$ the first $j$ numbers in the permutation do not form $[j],$ and $(n-i)!$ is the number of ways of permuting the higher indices $j>i.$ Such an index must exist by the well-ordering principle since all $n$ numbers form the set $[n].$ By repeatedly using the recurrence relation and $f(1)=1,$ we get $$f(6)=461.$$ The recurrence relation is also stated here.