Find the number of permutations satisfying the given criterion

combinationscombinatorics

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

Best Answer

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?

Related Question