Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$

Question

I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here).

Show that the total number of cycles of all even permutations of $[n]$ and the total number of cycles of all odd permutations of $[n]$ differ by $(−1)^n (n − 2)!$. Use generating functions.

I might be completely off the track here, but the way I thought of this problem is the following. A permutation can be written as a product of disjoint cycles, and a permutation is odd iff there is an odd number of even-length cycles.

The set of cycles partition $[n]$ into disjoint orbits, and thus the number of cycles of all odd permutations of $[n]$ should be equal to the number of partitions of $[n]$ into even parts, with an odd number of such parts (and similarly for the even permutations).

Is this right or have I misunderstood something? Also, I'm not quite sure how to proceed from here and how to set up the generating functions.

I did find this question, which might be of some use if my interpretation of this problem is correct.

However, I did not clearly see how one could end up with $(-1)^n (n-2)!$ from that.

Any help would be greatly appreciated :)

Answer 1

Here is an argument completely different from joriki’s; it is also a complete solution.

A cycle is an odd permutation iff its length is even, so a permutation written as a product of disjoint cycles is even iff an even number of the factors are even cycles. Let $\pi=\sigma_1\dots\sigma_k$ be a permutation of $[n]$ written as a product of $k$ disjoint cycles. Then $n=|\,\sigma_1|+\dots+|\,\sigma_k|$, so the parity of $n$ is the same as the parity of the number of cycles of odd length. Thus, $\pi$ has an even number of cycles of even length iff $n$ and $k$ have the same parity, i.e., iff $(-1)^{n+k}=1$.

Let $e_n$ be the total number of cycles in even permutations of $[n]$, let $o_n$ be the total number of cycles in odd permutations of $[n]$, and let $d_n=e_n-o_n$. The total number of permutations of $[n]$ with $k$ cycles is given by $\left[n\atop k\right]$, the unsigned Stirling number of the first kind. Each of these $\left[n\atop k\right]$ permutations contributes $k$ cycles to $e_n$ if $(-1)^{n+k}=1$, and to $o_n$ if $(-1)^{n+k}=(-1)$. Thus, each contributes $(-1)^{n-k}k$ to $d_n$, and it follows that

$$d_n=\sum_k(-1)^{n+k}k\left[n\atop k\right]\;.$$

Now $(-1)^{n+k}\left[n\atop k\right]=(-1)^{n-k}\left[n\atop k\right]$ is the signed Stirling number of the first kind, for which we have the generating function $$\sum_k(-1)^{n+k}\left[n\atop k\right]x^k=x^{\underline{n}}\;.\tag{1}$$

(Here $x^{\underline{n}}=x(x-1)(x-2)\cdots(x-n+1)$ is the falling factorial, sometimes written $(x)_n$.)

Differentiate $(1)$ with respect to $x$ to obtain

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=Dx^{\underline{n}}=(x-n+1)Dx^{\underline{n-1}}+x^{\underline{n-1}}\;,$$

where the last step is simply the product rule, since $x^{\underline{n}}=x^{\underline{n-1}}(x-n+1)$. But $$Dx^{\underline{n-1}}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}\;,$$ so

$$\sum_k(-1)^{n+k}k\left[n\atop k\right]x^{k-1}=\sum_k(-1)^{n-1+k}k\left[{n-1}\atop k\right]x^{k-1}+x^{\underline{n-1}}\;.\tag{2}$$

Now evaluate $(2)$ at $x=1$ to get $$d_n=(2-n)d_{n-1}+[n=1\text{ or }n=2]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$ and $d_2=0+[1=1]=1$, which by direct calculation are the correct values: the only permutation of $[1]$ is the identity, which is even and has one cycle, and the only permutations of $[2]$ are the identity, which is even and has two cycles, and the unique $2$-cycle, which is odd. It’s now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 2$: the induction step is

$$\begin{align*}d_{n+1}&=\Big(2-(n+1)\Big)d_n\\ &=(1-n)(-1)^n(n-2)!\\ &=(-1)^{n+1}(n-1)!\;. \end{align*}$$

Added: It occurs to me that there’s a rather easy argument that does not use generating functions. Let $\sigma$ be any $k$-cycle formed from elements of $[n]$; then $\sigma$ is a factor in $(n-k)!$ permutations of $[n]$. Moreover, exactly half of these permutations are even unless $n-k$ is $0$ or $1$. Thus, $\sigma$ contributes to $d_n$ iff $k=n$ or $k=n-1$.

There are $(n-1)!$ $n$-cycles; they are even permutations iff $n$ is odd, so they contribute $(-1)^{n-1}(n-1)!$ to $d_n$.

There are $n(n-2)!$ $(n-1)$-cycles: there are $n$ ways to choose the element of $n$ that is not part of the $(n-1)$-cycle, and the other $n-1$ elements can be arranged in $(n-2)!$ distinct $(n-1)$-cycles. The resulting permutation of $[n]$ is even iff $n-1$ is odd, i.e., iff $n$ is even, so they contribute $(-1)^nn(n-2)!$ to $d_n$.

It follows that $$\begin{align*}d_n&=(-1)^nn(n-2)!+(-1)^{n-1}(n-1)!\\ &=(-1)^n\Big(n(n-2)!-(n-1)!\Big)\\ &=(-1)^n(n-2)!\Big(n-(n-1)\Big)\\ &=(-1)^n(n-2)!\;. \end{align*}$$

Answer 2

Warning: This is a complete solution; you may want to read only a part of it to get you on the right track and then see if you can complete it.

The number of permutations of $[n]$ is $n!$, so the exponential generating function for the number of permutations is

$$\sum_{n=0}^\infty x^n=\frac1{1-x}\;.$$

The number of cycles containing all elements of $[n]$ is $(n-1)!$, so the exponential generating function for the number of cycles is

$$\sum_{n=1}^\infty \frac1nx^n=-\log(1-x)\;.$$

The exponential generating function for the number of ordered tuples of $k$ cycles together containing all elements of $[n]$ is therefore $(-\log(1-x))^k$.

The number of permutations of $[n]$ with $k$ cycles is the number of unordered tuples of $k$ cycles together containing all elements of $[n]$, so we have to divide by a factor of $k!$ for the number of permutations of the cycles; so the exponential generating function for the number of permutations of $[n]$ with $k$ cycles is $(-\log(1-x))^k/k!$. We can check this result by summing over $k$ to regain

$$\sum_{k=0}^\infty\frac{(-\log(1-x))^k}{k!}=\mathrm e^{-\log(1-x)}=\frac1{1-x}\;.$$

Now we just have to include a sign for the parity of the permutations. A permutation of $[n]$ with $k$ cycles has parity $(-1)^{k+n}$. To test the approach, let's first calculate the excess of the even permutations over the odd permutations, without counting the cycles. Including the factor $(-1)^k$ in the coefficients yields

$$\sum_{k=0}^\infty(-1)^k\frac{(-\log(1-x))^k}{k!}=\mathrm e^{\log(1-x)}=1-x\;,$$

and then taking into account the factor $(-1)^n$ yields the expected result, namely that the excess is $1$ for $n=0$ and $n=1$ and $0$ otherwise.

Now to count the total number of cycles we just have to include a factor $k$ in the sum:

$$ \begin{eqnarray} \sum_{k=0}^\infty(-1)^kk\frac{(-\log(1-x))^k}{k! } &=& \sum_{k=1}^\infty(-1)^k\frac{(-\log(1-x))^k}{(k-1)!} \\ &=& (1-x)\log(1-x) \\ &=& -x+\sum_{n=2}^\infty\frac{x^n}{n(n-1)} \\ &=& -x+\sum_{n=2}(n-2)!\frac{x^n}{n!}\;, \end{eqnarray} $$

and then taking into account the factor $(-1)^n$ from the parity yields the desired result for $n\ge2$.

P.S.: I just realized the factor $(-1)^n$ could have been dealt with a bit more elegantly by including it right from the start and writing $1+x$ everywhere instead of $1-x$.

Added: Brian's easier proof without generating functions made me wonder whether there's also an easier proof by induction. There is: Consider the cycle structures of all permutations of $[n]$, and add $n+1$ to each of them in all possible ways. For each cycle structure, there are $n$ ways of adding $n+1$ to one of the cycles and $1$ way of adding it as a cycle of its own.

If we add it as a cycle of its own, the parity is unchanged. Since there are equal numbers of permutations of both parities, the new cycle doesn't contribute to the result; the other cycles contribute the same excess as they did for $n$, namely $(-1)^n(n-2)!$ by the induction hypothesis.

On the other hand, if we add $n+1$ to one of the cycles, the parity changes while the number of cycles stays the same. Since there are $n$ ways of doing this for each cycle, this yields a contribution of $-n(-1)^n(n-2)!$. The total is therefore $(1-n)(-1)^n(n-2)!=(-1)^{n+1}((n+1)-2)!$.