# I calculated the number of permutations with no 2-cycles in two ways but I got 2 different results

I calculated the number of permutations in $S_n$ with no 2-cycles in two ways but I got 2 different results. The first time I used the principle of inclusion-exclusion and I got $\sum_{k=0}^n \frac{n!}{k!}\frac{1}{2^k}(-1)^k$ and I'm pretty sure that it's right. The second way is using generating functions. Using the exponential formula I calculated that the generating function of this type of permutations is $\frac{e^{-x^2/2}}{1-x}$. So it is $(\sum x^n)(\sum 1/n! (-1/2)^n x^{2n}$. If I make the product of these two series I got the series with coefficient $\sum_{k=0, k\;even}^n 1/(k/2)!(-1/2)^{k/2}$. Could you tell me where is the mistake?

This is the computation of inclusion-exclusion: we count the permutations with at least one 2-cycle. The number of permutation with at least k 2-cycles is $c_k=(n-2k)!\frac{\binom{n}{2}\binom{n-2}{2}\cdots\binom{n-2k+2}{2}}{k!}$. So the permutations with at least one 2-cycle are $\sum_{k=1}^n(-1)^kc_k$. So what we want is $n!-\sum_{k=1}^n\frac{n!}{k!}\frac{1}{2^k}(-1)^k=\sum_{k=0}^n\frac{n!}{k!}(-1/2)^k$. So it's probable that the mistake is in the computation of $(-1)^kc_k$. Does anyone see an expression for this?

-
I'm not sure what it means for a permutation to have no $2$-cycles, but your first formula gives $1/2$ for $n=1$. That doesn't seem to make sense under any interpretation. – Chris Eagle Nov 13 '11 at 3:03
you're right. I will post my computation so we can find the mistake. However permutation with no 2-cycles means that in its cycle decomposition there are no transposition. – Alex M Nov 13 '11 at 3:19

If $C$ is any set of positive integers, and $g_C(n)$ is the number of permutations of $[n]$ whose cycle lengths are all in $C$, then $$G_C(x)=\sum_{n\ge 0}g_C(n)\frac{x^n}{n!}=\exp\left(\sum_{n\in C}\frac{x^n}{n}\right)$$ is the exponential generating function for the $g_C(n)$. (Rather than derive it, I’ve simply quoted this from Theorem 4.34 in Miklós Bóna, Introduction to Enumerative Combinatorics.)

In your case $C=\mathbb{Z}^+\setminus\{2\}$, so it’s \begin{align*} G_C(x)&=\exp\left(\sum_{n\ge 1}\frac{x^n}n-\frac{x^2}2\right)\\ &=\exp\left(-\ln(1-x)-\frac{x^2}2\right)\\ &=\frac{e^{-x^2/2}}{1-x}, \end{align*} and your generating function is correct. Then

$$\frac{e^{-x^2/2}}{1-x}=\left(\sum_{n\ge 0}x^n\right)\left(\sum_{n\ge 0}\frac{(-1)^nx^{2n}}{n!2^n}\right),$$ and

$$[x^n]\left(\sum_{n\ge 0}x^n\right)\left(\sum_{n\ge 0}\frac{(-1)^nx^{2n}}{n!2^n}\right)=\sum_{k=0}^{\lfloor n/2\rfloor}\frac{(-1)^k}{k!2^k}.$$

Recall, though, that the coefficient of $x^n$ in $G_C(x)$ is not $g_C(n)$, but rather $\dfrac{g_C(n)}{n!}$, so $$g_C(n)=n!\sum_{k=0}^{\lfloor n/2\rfloor}\frac{(-1)^k}{k!2^k}.$$

As a quick check, this yields $g_C(1)=1$, $g_C(2)=2\left(1-\frac12\right)=1$, $g_C(3)=6\left(1-\frac12\right)=3$, $g_C(4)=24\left(1-\frac12+\frac18\right)=15$, and $g_C(5)=120\left(1-\frac12+\frac18\right)=75$, all of which are in agreement with the OEIS values.

For your inclusion-exclusion argument, $c_k=0$ for $k>\lfloor n/2\rfloor$, and $c_0=n!$, so what you actually want is $$\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^kc_k=\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\frac{n!}{k!2^k},$$ which is exactly what we just got with generating functions.

-

The sequence is here. You may find the discussion and references helpful.

-