4 ms·
Counting Cycles of a Permutation in Parallel
- Leon 17y agoThis 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!
- btilly 17y agoFor 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.