OFFSET
0,3
COMMENTS
Foata's bijection takes a permutation w with maj(w)=x to a permutation F(w) with inv(F(w))=x. Applying F repeatedly partitions the symmetric group into distinct orbits. F also preserves inverse descent sets.
REFERENCES
James Pfeiffer, personal communication.
LINKS
Dominique Foata and Marcel-Paul Schützenberger, Major Index and inversion number of permutations, Math. Nachr. 83 (1978), 143-159
EXAMPLE
The orbits of S_4 are:
[(1, 2, 3, 4)]
[(2, 1, 3, 4)]
[(2, 3, 1, 4)]
[(2, 3, 4, 1)]
[(3, 2, 1, 4)]
[(3, 2, 4, 1)]
[(3, 4, 2, 1)]
[(4, 3, 2, 1)]
[(2, 1, 4, 3), (4, 2, 1, 3), (2, 4, 1, 3)]
[(2, 4, 3, 1), (4, 2, 3, 1)]
[(1, 3, 2, 4), (3, 1, 2, 4)]
[(1, 3, 4, 2), (3, 1, 4, 2), (3, 4, 1, 2)]
[(1, 4, 3, 2), (4, 3, 1, 2)]
[(4, 1, 3, 2)]
[(1, 2, 4, 3), (4, 1, 2, 3)]
[(1, 4, 2, 3)]
CROSSREFS
KEYWORD
nonn,hard,more
AUTHOR
Austin Roberts, Oct 26 2011
STATUS
approved