How to find the number of permutations satisfying the given criterion

Question

I have a set of numbers, namely {1,2,3,4,5,6}.I want to find the number of permutations $a_1,a_2,a_3,a_4,a_5,a_6$ of the above mentioned set such that $a_1,...,a_k$ is not a permutation of $1,..k$ for any integer k, $1 \leq k \leq 5$

My approach:

I call a permutation unfavourable if that permutation does not belong to the required number of permutations, and favourable otherwise

1. I consider the case where $a_1 = 1$, all the permutations satisfying this criterion will be unfavourable. Thus, I dont have $5! = 120$ such unfavourable permutations

2. I consider all the permutations where the first two elements are a permutation of 1 and 2. The cases where $a_1 = 1$ is covered above, thus I have to consider the case when $a_1=2$ $a_2=1$, which if I am correct will give my $4! = 24$ unfavourable permutations

3. I now consider the permutations where the first 3 elements are a permutation of $1,2,3$ The permutations starting with $a_1=1$ and $a_1=2,a_2=1$ are considered in the above cases and hence I only consider the cases where the permutations start in $(3,1,2);(3,2,1);(2,3,1)$ giving me a total of 18 different unfavourable permutations.

Continuing thus and considering the permutations wherein the first 4 elements are a permutation of $1,2,3,4$ and the permutations wherein the first 5 elements are a permutation of $1,2,3,4,5$ and carefully computing the cases , taking care that they are not a repetition of the above cases, I am getting a total of 237 unfavourable cases, which when subtracted from 720, which is the total number of permutations, I get the answer 483.

However the given answer is 528, can anybody please correct me where I am going wrong, have I considered any case multiple number of times?

Also, alternative solutions are also welcome since I find this method of mine to be cumbersome

Answer 1

I would like to see a solution without the counting approach, but can't think of it myself sofar.

I count the cases in a slightly different order that is more convenient.

There are in total $6!=720$ different permutations.

The case $k=1$, exclude 120 permutations of the type $(1,\dots)$.

The case $k=5$, exclude 120 permutations of the type $(\dots,6)$.

If we combine them we extracted the 24 permutations of type $(1,\dots,6)$ twice, so combining $k=1$ and $k=5$ we can discard $120+120-24=216$ permutations.

The case $k=2$, excludes the additional 18 permutations $(2,1,\dots)$, where it is already used that the last digit cannot be a 6.

The case $k=4$, excludes the additional 18 permutations $(\dots,6,5)$, where it is already used that the first digit cannot be a 1.

But if we combine $k=2$ and $k=4$ we counted the $(2,1,\dots,6,5)$ twice. So in total adding the cases $k=2$ and $k=4$, exclude an additional $18+18-2=34$ permutations.

So we are left with considering $k=3$. In these to be discarded permutations the first three elements are 1,2,3 and the last three are 4,5,6. Taken into account the ones that are already excluded above, we only need to exclude the ones which are among $(2,3,1,\dots)$, $(3,1,2,\dots)$ and $(3,2,1,\dots)$ (From $k=1$ and $k=2$).

At the same time the exclusions made from $k=4$ and $k=5$ require us to only consider permutations of the types $(\dots,6,4,5)$, $(\dots,6,5,4)$, and $(\dots,5,6,4)$.

Since both requirements need to be satisfied for additional exclusions, there are $3 \times 3 = 9$ additional permutations to be excluded by adding the constraint $k=3$ to the others.

So in conclusion, we have to extract $216 + 34 + 9 = 259$ permutations and are left with $720-259=461$.

Answer 2

Instead of testing cases with $a_1$, we test cases with $a_6$

1. If $a_6=1$, all cases are favorable = $5!$
2. If $a_6=2$, all cases - those starting with $1 = 5!-1!\times 4!$
3. If $a_6=3$, all cases - those starting with $1,2 = 5!-2!\times 3!$
4. If $a_6=4$, all cases - those starting with $1,2,3 = 5!-3!\times 2!$
5. If $a_6=5$, all cases - those starting with $1,2,3,4 = 5! - 4!\times 1!$
6. If $a_6=6$, all cases are unfavorable = $0$

Adding all those together gives us 528.

In case you do not understand how to calculate the numbers, (e.g. those starting with $1,2,3 = 3!\times 2!$), here is the way:

Let us take the example, i.e. those starting with $1,2,3 = 3!\times 2!$.

We know that the first 3 numbers are formed by all permutations of $1,2,3$, and the next 2 numbers are formed by $4,5$ hence by the product rule it is $3!\times2!$

---

At first, I used a similar way like yours but after I found out that I have minus-ed several (quite many indeed!) numbers multiple times, and resulting in an answer less than the correct solution. Perhaps there is a similar mistake in yours, minus-ing numbers too much times?