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

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 :)

-
You seem to have misread the question. It asks for the total number of cycles in all parmutations of given parity. So it does not suffice to determine the cycle type for each parity, but for each cycle type you must multiply by the number of permutations with this cycle type, and then also by the number of cycles (over any such permutation). Also "number of partitions of $[n]$ into even parts, with an odd number of such parts" is not right; this would only be nonzero if $n\equiv2\pmod4$ (and even then not be the right number). –  Marc van Leeuwen Feb 25 '12 at 12:24

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]\;,\tag{3}$$ where the last term is an Iverson bracket. If we set $d_0=0$, $(3)$ yields $d_1=[1=1]=1$, which by direct calculation is the correct value: the only permutation of $[1]$ is the identity, which is even and has one cycle. It’s now a trivial induction to check that $d_n=(-1)^n(n-2)!$ for all $n\ge 1$: 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*}

-
Great, I like the direct argument. I'm wondering how one might show that exactly half the permutations are even unless $n-k$ is $0$ or $1$. One could a) use generating functions after all, b) use group theory (which none of our other proofs do), or c) use induction as in my added proof. Do you see an easier way? –  joriki Feb 25 '12 at 20:50
I noticed that in Stanley's book the second part of the exercise, to give a bijective proof, is marked $[3-]$ ("A few students may be capable of solving a $[3–]$ problem, while almost none could solve a $[3]$ in a reasonable period of time"). Your proof yields a bijective one: Every $k$-cycle for $k\le n-2$ is in bijection with another instance of itself with the remaining permutation multiplied by a transposition (say, of the two least remaining elements), and every $(n-1)$-cycle not containing, say, $1$ is in bijection with the $n$-cycle obtained by inserting the remaining element after $1$. –  joriki Feb 25 '12 at 21:41
@joriki: I don’t see an easier way. I didn’t actually think about how I knew that half of the permutations were even for $n>1$, so I guess that I’d have to say that I was using group theory. I actually came up with the second argument when I was thinking about a bijective proof (and then went to bed without looking any further!). It’s a nice problem. –  Brian M. Scott Feb 25 '12 at 22:47
Your added comment is too loosely formulated, and I first thought it was incorrect. You must be precise about what you are counting and how exactly to cancel (it does not suffice that the items you don't like can be canceled). As I see it now, you are counting pairs $(\pi,c)$ of a permutation $\pi$ and a cycle $c$ in $\pi$, which pair is counted with the sign of $\pi$. Now if $c$ is not of length $n$ or $n-1$, you can keep $c$ and replace $\pi$ by $\pi'$ obtained by transposing the first two elements not in $c$; this is an involution on those pairs and image contributes with opposite sign. –  Marc van Leeuwen Mar 4 '12 at 9:33
@Marc: I think it quite clear what I’m doing: I’m simply counting by cycle by cycle instead of permutation by permutation. I note that joriki apparently had little trouble following it. –  Brian M. Scott Mar 4 '12 at 9:47

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)!$.

-

Here is a solution that has the advantage of brevity. Start by observing that the sign of a permutation $\pi$ is given by $$\sigma(\pi) = \prod_{c\in\pi} (-1)^{|c|-1}$$ where the product is over all cycles $c$ of $\pi.$

Recall that the unmarked species of permutations by the number of cycles is given by $$\mathfrak{P}(\mathfrak{C}(\mathcal{Z})).$$

If we want to include the signs of these permutations we need to mark cycles with a variable $\mathcal{U}$ whose exponent indicates the cycle length minus one. This gives the modified species

$$\mathfrak{P}(\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots.)$$

We also want the cycle count so we mark all cycles with the variable $\mathcal{V},$ finally getting the species $$\mathfrak{P}(\mathcal{V}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{V}\mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^2\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{V}\mathcal{U}^3\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots.)$$

Switching to generating functions we obtain the generating function $G(z, u, v)$ where $$G(z, u, v) = \exp\left( vz + vu\frac{z^2}{2} + vu^2\frac{z^3}{3} + vu^3\frac{z^4}{4} + vu^4\frac{z^5}{5} + \cdots \right).$$ This is $$G(z, u, v) = \exp \left(\frac{v}{u}\left( uz + u^2 \frac{z^2}{2} + u^3 \frac{z^3}{3} + u^4 \frac{z^4}{4} + u^5 \frac{z^5}{5} + \cdots \right) \right)$$ which finally gives $$G(z, u, v) = \exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right).$$ Now to obtain the total cycle count differentiate by $v$ and set $v=1$ to get $$H(z, u) = \left.\frac{d}{dv} G(z, u, v)\right|_{v=1} = \left.\exp \left( \frac{v}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right)\right|_{v=1} \\ = \exp \left( \frac{1}{u} \log \frac{1}{1-uz} \right) \left( \frac{1}{u} \log \frac{1}{1-uz} \right).$$ Observe that $$\frac{1}{2} H(z, 1) + \frac{1}{2} H(z, -1)$$ gives the contribution from even permutations and $$\frac{1}{2} H(z, 1) - \frac{1}{2} H(z, -1)$$ from odd ones, so that $$H(z, -1)$$ yields the difference we want to compute. Setting $u=-1$ we obtain $$H(z, -1) = \exp \left( - \log \frac{1}{1+z} \right) \left( - \log \frac{1}{1+z} \right) \\=\left( -\log \frac{1}{1+z} \right) \exp\left(\log(1+z)\right) = -(1+z)\log\frac{1}{1+z}.$$

To conclude it remains to extract coefficients from this exponential generating function, and we get $$n! [z^n] H(z, -1) = - n! [z^n] (1+z)\log\frac{1}{1+z} = - n! \left(\frac{(-1)^n}{n} + \frac{(-1)^{n-1}}{n-1}\right) \\= - (-1)^n \times n! \times \left(\frac{1}{n}-\frac{1}{n-1}\right) = (-1)^{n+1} \times n! \times \frac{-1}{n(n-1)} \\= (-1)^n \times (n-2)!.$$

Nice page I have to say.

Important note. I just noticed that the above is a duplicate. I solved the same problem a little less than a year ago using the same method and the link to it can be found under "linked" in the right side bar.

-