Counting Cycles of a Permutation in Parallel

This has really become my favorite blog. Lipton is great to read to get a survey of different math/cc topics. Plus he's holding out hope P=NP!

For anyone who is curious why the theorem is true, here is a quick sketch of a possible proof.

First prove that both sides of the equation are (mod 2) invariant if you swap the labeling of (i, i+1). (That is if we keep the permutation alone and swap the two labels, we don't change either side.) This allows us to rewrite any permutation so that it takes a canonical form where each cycle takes the form i -> i+1 -> ... -> i+j -> i. Then prove the theorem for permutations of that form.