3
$\begingroup$

Determine the number of permutations of $ 1,2, \ldots ,8$ in which no even integer is in its natural position. Please solve this using concept of derangements.

$\endgroup$

closed as off-topic by ml0105, choco_addicted, M. Vinay, colormegone, David K May 28 '16 at 19:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – ml0105, choco_addicted, M. Vinay, colormegone, David K
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Well solve it then, whats the problem! $\endgroup$ – Alex May 28 '16 at 14:33
  • $\begingroup$ @Alex my answer not matching. If we had to calculate $D_4$ $\endgroup$ – mathlover May 28 '16 at 14:34
  • 3
    $\begingroup$ You didn't show any work, how am i supposed to know! $\endgroup$ – Alex May 28 '16 at 14:43
  • 3
    $\begingroup$ @Ayush: The answer is not $D_4$: that’s just the number of permutations that derange the even numbers amongst themselves and leave the odd numbers fixed. The permutation that interchanges $1$ and $2$, $3$ and $4$, $5$ and $6$, and $7$ and $8$ leaves no even integer in its natural position and is not counted in your $D_4$. $\endgroup$ – Brian M. Scott May 28 '16 at 15:48
  • 3
    $\begingroup$ What does "using concept of derangements" mean? Is it enough to use the same technique, i.e. Inclusion/Exclusion? $\endgroup$ – André Nicolas May 28 '16 at 16:07
4
$\begingroup$

Let $S$ be the set of all permutations of $\{1, 2, . . . , 8\}$. Let $A_1$ be the set of all permutations in $S$ which has $2$ in it natural position; $A_2$ be the set of all permutations in $S$ which has $4$ in it natural position; $A_3$ be the set of all permutations in $S$ which has $6$ in it natural position and $A_4$ be the set of all permutations in $S$ which has $8$ in it natural position. Then

$|A_1| = |A_2| = |A_3| = |A_4| = (8 − 1)!$,

$|A_1 ∩ A_2| = |A_1 ∩ A_3| = |A_1 ∩ A_4| = |A_2 ∩ A_3| = |A_2 ∩ A_4| = |A_3 ∩ A_4| = (8 − 2)!$,

$|A_1 ∩ A_2 ∩ A_3| = |A_1 ∩ A_2 ∩ A_4| = |A_1 ∩ A_3 ∩ A_4| = |A_2 ∩ A_3 ∩ A_4| = (8 − 3)!$,

$|A_1 ∩ A_2 ∩ A_3 ∩ A_4| = (8 − 4)!$. Then the set of permutations of $\{1, 2, . . . , 8\}$ in which no even integers are in their national positions is $\bar A_1 ∩ \bar A_2 ∩ \bar A_3 ∩ \bar A_4 $ and the number of the elements is $8! − 4 · 7! + 6 · 6! − 4 · 5! + 4! = 24024. $ $\blacksquare$

(And also we can use this identity which is related to derangement : $n! = \Sigma _{k=0}^n \binom {n}{k}D_{n-k}= \Sigma _{k=0}^n \binom {n}{k}D_{k}.$

Proof: Let $S$ be the set of all permutations of $\{1, 2, . . . , n\}$. Let $A_k$ be the set of all permutations that $k$ integers are fixed at their positions. Then $|S|= n!$ and $|A_k| = \binom{n}{k}D_{n-k}$ . The identity follows from the disjoint union $S = \cup^{n}_{k=0} A_k.$)

$\endgroup$
3
$\begingroup$

The total number of permutations of 1-8 is $8!$. Of these $7!$ fix any one given even number, $6!$ fix two, $5!$ fix three and $4!$ fix all four. So by inclusion-exclusion the number fixing none is $8!-4\cdot7!+6\cdot6!-4\cdot5!+4!=24024$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.