I'm trying to count the number of permutations of $\{ 1,...,n\}$ that don't contain a transposition (that is, whose disjoint cycle decompositions contain no cycles of length 2). I read that the result is $\sum_{k=0}^{\lfloor n/2\rfloor}\,\frac{(-1)^kn!}{2^kk!}$, but don't understand where this comes from.
I assume the idea is to use inclusion-exclusion on sets $A_i$ of all permutations with $i$ transpositions - putting these together suggests that I need to show $|A_{i_1} \cap ... \cap A_{i_k}| = \frac{(n-k)!}{2^k}$ for $i_1 \leq ... \leq i_k$, since then we have $\sum |A_{i_1} \cap ... \cap A_{i_k}| = {n\choose k}\frac{(n-k)!}{2^k} = \frac{n!}{2^k k!}.$
However, I get $|A_{i_1} \cap ... \cap A_{i_k}| = |A_{\max \{ i_1, ... , i_k \}}| $ and $|A_j| = \frac{n!}{2^j}$, which doesn't seem to help.
Let $A_{i,j}$ be the set of permutations $w$ of $[2n]$ in which $(i,j)$ is a transposition in the cycle decomposition of $w$. Then we seek the cardinality of $$ \bigcap_{\{i,j\}\subset[n], i\neq j} \bar{A_{i,j}} $$ Let $$ S_m= \sum|A_{i_1,j_1}\cap \dotsb \cap A_{i_m,j_m}|\quad (0\leq m\leq n) $$ where the summation is over all $m$ element subsets $E=\{\{i_1,j_1\},\dotsc, \{i_m,j_m\}\}$ of the collection of all two element subsets of $[2n]$. Note that if the elements of $E$ don't happen to be pairwise disjoint the contribution to the sum is zero. Set $S_0=(2n)!$. Then note that the quantity we seek may be expressed as $$ \sum_{m=0}^{n}(-1)^mS_m. $$ But $$ S_m=\binom{2n}{2m}\frac{(2m)!}{2^mm!}(2n-2m)!=\frac{(2n)!}{2^m m!}.$$ Indeed we choose $2m$ elements from $[2n]$ to use for transpositions. There are $\frac{(2m)!}{2^mm!}$ permutations permuations of these $2m$ elements with exactly $m$ transpositions and finally we permute the remaining $2n-2m$ elements. The result follows