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.
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!$$