Permutations and number of lists How many permutations $a_1, a_2, a_3, a_4$ of $1, 2, 3, 4$ satisfy the condition that, for $k = 1, 2, 3$, the list $\{a_1, \dots, a_k\}$ has a number greater than $k$?
I am not sure if I understand what the question is asking. Probably not, since my answer is wrong.
What I found is:
For $k = 1$,
$\{2\},\{3\},\{4\}$
for $k = 2$,
$\{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}$
for $k = 3$,
$\{1,2,4\}, \{1,3,4\}, \{2,3,4\}$
That is $11$, but the answer is $13$.
 A: There are only $24$ permutations of four elements, so we might as well use brute force.

*

*Suppose $a_1=4$, then all three conditions are automatically satisfied – for all of $k=1,2,3$, it is true that the first $k$ elements of the permutation have a number larger than $k$. This gives $6$ permutations.

*Suppose $a_2=4$. Then the $k=2,3$ conditions are satisfied and the only remaining restriction is $a_1\ne1$. This gives $4$ permutations.

*The $k=3$ condition is not satisfied if $a_4=4$, so let $a_3=4$. If $a_1=3$, all conditions are satisfied ($2$ more ways). If $a_4=3$, the $k=2$ condition cannot be satisfied. If $a_2=3$, the only way to satisfy all conditions is $a_1=2$ and $a_4=1$.

Summing it all up gives $13$ admissible permutations.
A: This question seems to work best by looking at it from sub-lists that are excluded.
For $k=1$, we cannot start a permutation with $1$, so we lose $6$ from the starting $24$.
Then for $k=2$, we cannot have $[1,2], [2,1]$, but we have already eliminated $[1,2]$, and so we can safely remove $2$ more permutations ($[2,1,3,4], [2,1,4,3]$).
And finally for $k=3$, from the six permutations of the invalid $[1,2,3]$, we can remove $[1,.,.]$ and $[2,1,.]$, which means that we need to remove $[2,3,1,4],[3,1,2,4]$ and $[3,2,1,4]$, another $3$.
So the final answer is $24-6-2-3=13$.
