## 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

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

which simplifiies to

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

as an exponential generating function for permutations, where z marks size and u marks number of cycles. That is,

where is the number of permutations of [n] with k cycles.

Finally, let u = -1. Then we get

and taking the coefficient of zn on both sides for any n ≥ 2 and multiplying through by n!, we get

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 for fixed n is

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

vishal 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.)