4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Sergio
    Commented Dec 23, 2020 at 12:01
  • $\begingroup$ 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$? $\endgroup$ Commented Dec 23, 2020 at 12:18

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .