Let $A$ be the set of all permutations $a_1, a_2,\dots,a_6$ of $1, 2, \dots, 6$ such that $a_1, a_2, \dots, a_k$ is not a permutation of $1, 2, \dots, k$ for any $k$ , $1\leq k \leq 5$. Then the number of elements in $A$ is $528$.
Can anyone please help me by giving any hint. I have no idea how to start.
On
I was trying to solve this problem in Brute-force method.. Basically I need to find the number of elements in $A$ which is the set of all $\phi \in \sum_6$ such that for no $k$ with $1 \leq k \leq 5$ do we have $\phi([1,k]) \subset [1,k]$.
Case 1: Let's Find out the number of $\phi \in \sum_6$ such that $\phi([1,5]) \subset [1,5]$.
Here $[1 , 2, 3, 4 , 5]$ denotes the set of all permutations of the elements $1 , 2, 3, 4 ,5$. We will get $5!$ such permutations.
Case 2: Let's Find out the number of $\phi \in \sum_6$ such that $\phi([1,4]) \subset [1,4]$ and do not belong to case 1. $[1 , 2, 3, 4] (5 \,6)$ are such elements . Here $[1 , 2, 3, 4]$ denotes the set of all permutations of the elements $1 , 2, 3, 4$. We will get $4!$ such permutations.
Case 3: Let's Find out the number of $\phi \in \sum_6$ such that $\phi([1,3]) \subset [1,3]$ and do not belong to case 1 and case 2. $[ 1, 2, 3] (4 \, 5 \, 6)$ , $[ 1 , 2 , 3] (4 \, 6 \, 5)$ , $[ 1 , 2 , 3] (4 \, 6)$ are such elements. So total number of such elements is $3! .3 = 18$
Case 4: Let's Find out the number of $\phi \in \sum_6$ such that $\phi([1,2]) \subset [1,2]$ and do not belong to case 1 and case 2 and case 3.
$[ 1 , 2] (3 \, 6) (4 \, 5)$ ,$[ 1 , 2] (3 \, 6) [4] [5]$ , $[ 1 , 2] ( 3 \, 4 \, 6)$ , $[ 1 , 2] (3 \, 6 \, 4)$ , $[ 1 , 2] (3 \, 5 \, 6)$ , $[ 1 , 2] (3 \, 6\, 5)$ , $[ 1 , 2] ( 3 \, 5) (4 \, 6)$ , $[ 1 ,2] ( 3 \, 4 \, 5 \,6)$
We will get total $ 2 . 6 + 2 + 2.3!=26 $
Case 5: Let's Find out the number of $\phi \in \sum_6$ such that $\phi(1 )= 1$ and do not belong to case 1 and case 2 , case 3 , case 4.
$[1] (2 \, 3 \, 4 \, 5 \, 6)$ -- We will have 4! such cases.
$[1] (2 \, 3 \, 5 \, 6)$ ----We will have $3!$ such cases.
$[1] (2 \, 3 \, 4 \, 6)$ ----We will have $3!$ such cases.
$[1] (2 \, 4 \, 5 \, 6)$ ----We will have $3!$ such cases.
$[1] [3,4] (2 \, 5 \, 6)$ ----We will have $12$ such cases.
$[1] [3 , 4,5] (2 \, 6)$ ----We will have $3!$ such cases.
$[1] (2 \, 5) ( 3 \, 6)$
$[1] (2 \, 4) ( 3 \, 6)$
$[1] (2 \, 5) ( 4 \, 6)$
$[1] (2 \, 4) ( 3 \, 5 \, 6)$ ----We will have $2$ such cases.
$[1] (2 \, 5) ( 3 \, 4 \, 6)$ ----We will have $2$ such cases.
$[1] (4 \, 6) ( 2 \, 3 \, 5)$ ----We will have $2$ such cases.
$[1] (3 \, 6) ( 2 \, 4 \, 5)$ ----We will have $2$ such cases.
So we are getting 259 total elements which are to be excluded from the set of all permutations of $1 , 2 , 3, 4 ,5 ,6$.
So the number of elements in $A$ is $(720 - 259) = 461$.
Can anyone please check my solution if I miss out any cases or any repetition.
Thank You in advance..
Consider the ordered sums $k_1+\cdots+k_m=6$ and the permutations that permute the first $k_1$, the next $k_2$ etc. elements among themselves. Every permutation is associated with exactly one of these sums, and you want to count the ones that are associated with the trivial sum $6=6$. We can partially order the sums by saying that $s_1\lt s_2$ if $s_1$ arises from $s_2$ by combining summands. This partial order corresponds to the partial order of the subsets of the five $+$ operators in $1+1+1+1+1+1$ by inclusion.
The Möbius function for this poset yields a coefficient $+1$ for every sum with an odd number of summands and $-1$ for every sum with an even number of summands (corresponding to the standard Möbius function for subsets ordered by inclusion). Now, for each unordered partition of $6$, find the number of ordered sums that correspond to it and the number of permutations that correspond to each of those sums, and add up the products with the corresponding signs, yielding (in the order $6$, $5+1$, $4+2$, $3+3$, $4+1+1$, $3+2+1$, $3+1+1+1$, $2+2+2$, $2+2+1+1$, $2+1+1+1+1$, $1+1+1+1+1+1$):
$$ 1\cdot6!-2\cdot5!-2\cdot4!\cdot2!-1\cdot3!\cdot3!+3\cdot4!+6\cdot3!\cdot2!-4\cdot3!+1\cdot2!^3-6\cdot2!^2+5\cdot2!-1=461\;. $$
This agrees with the number in the OEIS sequence and doesn't agree with yours, so it seems that either your problem statement or your result is wrong.