2
$\begingroup$

I am interested in determining $e_n$, the number of permutations of $\{ 1,2 \dots 2n\}$ where we allow even numbers to be fixed points, but where odd numbers are not allowed to be fixed points.

This really feels like a homogeneous inclusion-exclusion principle. Because first we need to include all permutations, so $(2n)!$, now we have overcounted, so we subtract the ones that fix one element, but the ones that fix one element are part of the ones that fix two elements, so we subtracted too much, we need to compensate ... I think this should be of the form $$ e_n =\sum_{k=0}^{2n} (-1) ^k\binom{2n}{k} (2k)! (2n-2k)!$$

I have not really taken into account here that we can only fix half of the elements though. How do I do this?


As a second part I want to show that this is equivalent to $$ e_n = \sum_ {k=0}^n \binom n k d_ {2n-k}$$ Where $d_{2n-k}$ denotes derangement of $2n-k$ elements.

Here it seems that we make some clever division. Again, we have $2n$ elements in total, but we decide to split it as follows: first we count all derangements of every single of the $2n$ elements, but here we are counting too little, because even elements can actually appear as fixpoints. We then count derangements of 2n-1 elements, where we simply allow $1$ element to be fixed, the binomial tells us how many elements there are that can be fixed. Now we fix two even elements $\dots$ in the end we fix all even elements and the sum of all these permutations is $e_n$.

$\endgroup$
  • $\begingroup$ Is there good reason to imagine that the answer is sensible? What is the result for $n≤10$, say? $\endgroup$ – lulu Jan 25 at 20:24
  • 3
    $\begingroup$ When I try inclusion/exclusion I get $$\sum_{k=0}^n(-1)^k\binom nk(2n-k)!.$$ $\endgroup$ – Lord Shark the Unknown Jan 25 at 20:35
  • $\begingroup$ oh yeah, because you can only fix $0 \leq k \leq n$ elements. Not all of them obviously! $\endgroup$ – Wesley Strik Jan 25 at 20:46
  • $\begingroup$ I think I managed to answer my own question now :) $\endgroup$ – Wesley Strik Jan 25 at 20:56
  • 1
    $\begingroup$ See OEIS A033815 $\endgroup$ – Henry Jan 25 at 20:57
0
$\begingroup$

The idea is that we first forget the restriction and simply permute all objects. This gives us $2n!$ - we have definitely overcounted here. We need to subtract all permutations that fix one odd number and we need to pick which odd number this is, this gives us $\binom{n}{1}(2n-1)!$. Now we removed the permutation that fixes number $x$, but which also happened to fix $y$ and the permutation that fixed $y$, but also happened to fix $x$- we removed it twice - oops! We need to add one such permutation that fixes two odd numbers else the amounts don't add up. We can do this in $\binom{n}{2}(2n-2)!$ ways. We continue over and under counting by the principle of inclusion-exclusion and get.

$$ \sum_{k=0}^n(-1)^k\binom nk(2n-k)!$$

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