# 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$$.

• Take this with a grain of salt but for $k=3$ you could include $\{3,1,4\}$ and $\{2,1,4\}$. Don't forget that you are working with a list not a set and that you have permutations, this means that order matters and $\{3,1,4\} \neq \{1,3,4\}$ for example. However, given you understood the question which I think you did, the same logic concludes to conclude answer is greater than $13$ since we can do this on some other places as well. Commented Dec 23, 2020 at 12:01
• To rephrase, how many permutations $(a_1, a_2, a_3, a_4)$ of the set $\{1, 2, 3, 4\}$ have $a_k > k$ for some $k$? Commented Dec 23, 2020 at 12:18

## 2 Answers

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.

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$$.