Given a permutation A on the set [n], is there a way to determine the maximum number of disjoint cycles of AC where C ranges over all n-cycles on [n]? For which class of permutations A, this problem has been studied before? Thanks
First decompose A into a product of disjoint cycles. Now I claim that the maximum number of disjoint cycles in the product of a k-cycle with an n-cycle over all n-cycles is k+1. Each cycle can be further decomposed into a product of transpositions of the form (a,b_1)(a,b_2)..(a,b_k), i.e., with a single pivot a. Then the maximizing n-cycle should be of the form (a,b_1,b_2,..,b_k,..). So by induction, the answer seems to be n - # disjoint cycles of A + 1 = HammingDistance(A, id) + 1.
Thanks for your answer! I think you are right. By the way, how to define the hamming distance? view A and id as one-line sequence?
Hamming distance between two permutations a and b is defined to be the minimum number of transpositions needed to bring a to b. If you express a^{-1} b as a one-line sequence, then Hamming distance is n - the number of fixed points.
I found that D. Zagier and Richard Stanley have studied this question before. If you are interested, their papers can be found on the internet.
Please help me with titles of the papers or copies of them if u have
Here is an easy example. Write A as a product of k cycles, including the 1-cycles, so that all n symbols appear. Post-multiply it by the n-cycle with the symbols in the reverse order. The product is one k-cycle permuting the last elements in each cycle, and n-k fixed points, giving the n-k+1 cycles mentioned previously. Is it so obvious that this is the maximum?
The titles of the papers I mentioned are something like:
Zagier, on the distribution of cycles....
Stanley, two enumerative results on product of cycles...
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics