Simple question but I just need a little tip to finish it.
we are given $A=\{1,2,3…,2n-1,2n\}$ the set of all integers between and including $1$ and $2n$.
We are asked how many different permutation are there on $A$ such that there are no even numbers that are fixed points?
My solution
Overall there are $(2n)!$ permutations. Let's count those that have an even fixed point:
If there is a single fixed point, then we can have $n$ values to choose from for a fixed point, and then we have $(2n-1)!$ ways to permute to other digits. so:
We will see that there are $n(2n-1)!$ permutations with a single even fixed point. due to same logic, for permutation with 2 even fixed points, there are $\binom{n}{2}(2n-2)!$
So overall,using inclusion-exclusion there are $n(2n-1)!-\binom{n}{2}(2n-2)!+\binom{n}{3}(2n-3)!-…+(-1)^{2n+1}n!$ permutations with an even number as a fixed point.
Is there anyway to sum this? Because I can't write: The answer is $(2n)!-(n(2n-1)!-\binom{n}{2}(2n-2)!+…+n!)$. I need an actual closed formula. not "$…$"
Best Answer
In your line "If there is a single fixed point" there are not $(2n-1)!$ ways to permute the rest of the digits, because you need to avoid fixed points. You can do what you are trying, but need the number of derangements of the non-fixed points. This is basically a factor of $e$
You are not using inclusion-exclusion as you are avoiding double counting entirely by specifying an exact number of fixed points. You therefore should have all plus signs in your expression of the number of permutations with an even fixed point.
That said, I don't have a sum of the corrected expression.