A195931 The number of orbits in S_n by the action of Foata's bijection.

1, 1, 2, 5, 16, 56, 236, 998, 4544, 20346

Offset: 0

Author

Austin Roberts, Oct 26 2011

Keywords

• nonn
• hard
• more

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.

Examples

			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)]
		

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

Crossrefs

Cf. A195931, A195924, A065161