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?

  • $\begingroup$ 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. $\endgroup$ – Chris Eagle Nov 13 '11 at 3:03
  • $\begingroup$ 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. $\endgroup$ – Mec 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.


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.