10 February 2008

Splitting permutations of [n] into two classes

The number of permutations of [n] with an even number of cycles and with an odd numbers of cycles are equal, for all n ≥ 2. (I assume this is a standard result, just because anyone who's stared at the Stirling numbers for long enough would think of it, but I don't recall hearing it before.)

Here's a proof which relies on bivariate generating functions. Note that a permutation can be viewed a set of directed cycles. In the notation of combinatorial classes, we write this
\cal{P} = \hbox{Set}(\mu \hbox{ Cyc}(\cal{Z}))

Now, there are (n-1)! cycles on an n-element set (order the n elements in n! ways, but then divide by n for the rotation) giving the generating function
z + 1! {z^2 \over 2!} + 2! {z^3 \over 3!} + 3! {z^4 \over 4} + \cdots

which simplifiies to
z + {z^2 \over 2} + {z^3 \over 3} + {z^4 \over 4} + \cdots

which is just log 1/(1-z).
The mark μ then becomes the variable u, and taking sets corresponds to exponentiation, so we have
P(z,u) = \exp( u \log (1-z)^{-1}) = (1-z)^{-u}

as an exponential generating function for permutations, where z marks size and u marks number of cycles. That is,
(1-z)^{-u} = \sum_{n,k} {1 \over n!} \left[ {n \atop k} \right] z^n u^k

where $\left[ {n \atop k} \right]$ is the number of permutations of [n] with k cycles.

Finally, let u = -1. Then we get
1-z = \sum_{n,k} {1 \over n!} \left[ {n \atop k} \right] z^n (-1)^k

and taking the coefficient of zn on both sides for any n ≥ 2 and multiplying through by n!, we get
0 = \sum_{k}  \left[ {n \atop k} \right] (-1)^k

But on the right-hand side, we get a contribution of +1 for each permutation of [n] with an even number of cycles, and -1 for each permutation with an odd number of cycles. Thus those two sets are equal in cardinality.

I feel like this is a standard result, but I hadn't seen this proof before coming up with it myself. There's a similar proof that doesn't require the bivariate generating function machinery; the generating function of the numbers $\left[ {n \atop k} \right]$ for fixed n is
\sum_k \left[ {n \atop k} \right] z^k = z(z+1)(z+2) \ldots (z+n-1)

and let z = -1 here. And I may have even seen a bijective proof of this fact, which gives a bijection between permutations of [n] with an odd number of cycles and an even number of cycles.

By the way, the analogous result that, say, one-third of permutations of [n] have a number of cycles divisible by 3, one-third have 3k+1 cycles for some k, and one-third have 3k+2 cycles for some k isn't true. (It should be approximately true, though, but that doesn't seem particularly interesting.)

Edited, 3:24 pm: See the comments for a bijective proof offered by Jeremy Henty; it really is quite simple but eluded my grasp this morning.


Anonymous said...

A bijective proof is quite straightforward: if s is a permutation and t is a 2-cycle, then t.s has either one more cycle than t (if t interchanges elements in the same cycle of s, because it splits that cycle into two) or one less (if t interchanges elements in different cycles of s, because it joins those cycles together). Ergo, multiplication by t is a bijection that reverses the parity of the number of cycles.

Jeremy Henty

Anonymous said...

I think this result is a common one in an undergraduate abstract algebra course, and the bijective proof provided by Jeremy is the usual one. Fraleigh's book does contain such a proof.

CarlBrannen said...

I actually liked the generating function argument more. I haven't seen that sort of combinatorics for years, and it was one of my favorite tools when I was an undergrad math major.

Anonymous said...

In general, I like generating function arguments too. And, I do like this one in particular.

A small typo: the second box containing the infinite series should have (3!z^4)/4! as its fourth term.

(The second comment btw is mine.)