
120 Combinatorics of Permutations, Second Edition
PROOF By Theorem 3.53, we need to compute
G
C
(x)=exp
x +
x
3
3
+
x
5
5
+ ···
=exp
⎛
⎝
n≥0
x
2n+1
(2n +1)!
⎞
⎠
.
Now note that taking derivatives, we have
⎛
⎝
n≥0
x
2n+1
2n +1
⎞
⎠
=
n≥0
x
2n
=
1
1 − x
2
=
1
2(1 − x)
+
1
2(1 + x)
.
Therefore,
n≥0
x
2n+1
2n +1
=
1
2
ln
(1 − x)
−1
+ln(1+x)),
and so
G
C
(x)=exp
1
2
ln
(1 − x))
−1
+ln(1+x)
=
1+x
1 − x
,
which was to be proved.
COROLLARY 3.59
For all positive integers n, the number of permutations of length 2n that
have odd cycles only is ODD(2n)=(1· 3 · 5 ···(2n − 1))
2
=(2n − 1)!!
2
.
Similarly, the number of permutations of length 2n +1 that have odd cycles
only is ODD(2n +1)=(1· 3 · 5 ···(2n − 1))
2
(2n +1)=(2n