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
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
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.
4 comments:
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
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.
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.
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.)
Post a Comment