# Fixed Point with Permutation

I have this homework question I'm kind of stumped on...

"A permutation of the numbers $(1,2,3,\ldots,n)$ is a rearrangement of the numbers in which each number appears exactly once. For example, $(2,5,1,4,3)$ is a permutation of $(1,2,3,4,5)$.

Let $\pi = (x_1,x_2,x_3,\ldots,x_n)$ be a permutation of the numbers $(1,2,3,\ldots,n)$. A fixed point of $\pi$ is an integer $k~(1\le k\le n)$ such that $x_k=k$. For example, $4$ is a fixed point of the permutation $(2,5,1,4,3)$.

How many permutations of $(1,2,3,4,5,6,7)$ have at least one even fixed point?"

Here's my work so far. Am I going in the right direction? Should I be thinking differently?

$(1)$ can have 1 fixed point permutation.

$(1,2)$ can have 1 fixed point permutation

$(1, 2, 3)$ can have 4 fixed point permutations?

$(1, 2, 3, 4)$ can have 15 fixed points?

I couldn't find any correlations or patterns here...

$(1)$ can have 0 even fixed point permutations

$(1, 2)$ can have 1 even fixed point permutation

$(1, 2, 3)$ can have 2 even fixed point permutations

$(1, 2, 3, 4)$ can have 6 even fixed point.

It's not factorials, or triangular numbers, so I'm kind of stuck here. What should I do next?

• Search oeis. You will probably find it there – Per Alexandersson Jun 18 '15 at 1:21
• The opposite problem is counting derangements (permutations with no fixed points). You can google this keyword for more information. In particular, you can count the number of derangements using the inclusion-exclusion principle. – whacka Jun 18 '15 at 1:24

There are $7!$ permutations of the set $\{1,...,7\}$. $6!$ permutations fix $2$, $6!$ fix $4$ and $6!$ fix $6$. $5!$ permutations fix any two elements from $\{2,4,6\}$ and $4!$ permutations fix all three.
So the total number of permutations that fix at least one element from $\{2,4,6\}$ is $3*6!-3*5!+4!=1824$ (by the inclusion-exclusion principle).