Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 4 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.