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?
 A: 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.
A: The sequence is here. You may find the discussion and references helpful. 
