1
$\begingroup$

How many permutations of $1,\ldots,8$ are there in which no even number appears in its natural position?

-Our teacher had us do a similar exercise to this one that looked for permutations without the patterns $12,34,56,78$; although I was able to complete it, I am unsure as to how to do this one, Any help is appreciated.

$\endgroup$
  • $\begingroup$ What is meant by "in its natural position"? Do you mean no even number is fixed by the permutation? $\endgroup$ – kccu Nov 18 '15 at 21:04
  • $\begingroup$ I believe it to mean that 2 wouldn't be in the 2nd place and 4 wouldn't be in the 4th place and so on... $\endgroup$ – jeremysanchez50 Nov 18 '15 at 21:05
  • $\begingroup$ You could consider the total number of permutations and subtract the number of permutations that have at least one even number in its natural position using the inclusion-exclusion principle. $\endgroup$ – Marcus Andrews Nov 18 '15 at 21:15
  • $\begingroup$ That was the conceptual idea I was going for, but how would I represent the number of permutations that have at least one even number in its natural position? $\endgroup$ – jeremysanchez50 Nov 18 '15 at 23:58
1
$\begingroup$

A number is a fixed point of a permutation if the permutation maps the number to itself.

To find the number of permutations in which no even number is a fixed point, you must subtract the number of permutations that contain at least one fixed point from the total number of permutations of the finite sequence $1, 2, 3, 4, 5, 6, 7, 8$.

There are $\binom{4}{1}$ ways to select one of the even numbers to be a fixed point of the permutation. For each such fixed point, we can arrange the remaining seven numbers of the sequence in $7!$ ways.

There are $\binom{4}{2}$ ways to select two of the even numbers to be fixed points of the permutation. For each such pair of fixed points, we can arrange the remaining six numbers of the sequence in $6!$ ways.

There are $\binom{4}{3}$ ways to select three of the even numbers to be fixed points of the permutation. For each such selection, we can arrange the remaining five numbers of the sequence in $5!$ ways.

There are $\binom{4}{4}$ ways to select all four even numbers to be fixed points of the permutation. For each such selection, we can arrange the remaining four numbers of the sequence in $4!$ ways.

By the Inclusion-Exclusion Principle, the number of sequences in which at least one even number is a fixed point of the permutation is $$\binom{4}{1}7! - \binom{4}{2}6! + \binom{4}{3}5! - \binom{4}{4}4!$$

Since there a total of $8!$ permutations of the eight numbers, the number of permutations in which no even number is a fixed point is $$8! - \binom{4}{1}7! + \binom{4}{2}6! - \binom{4}{3}5! + \binom{4}{4}4!$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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