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?
Best Answer
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).