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,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

Table of n, a(n) for n=0..9.

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

Cf. A195931, A195924, A065161

Sequence in context: A052891 A352905 A052815 * A350906 A082789 A234278

Adjacent sequences: A195928 A195929 A195930 * A195932 A195933 A195934

Keyword

nonn,hard,more

Author

Austin Roberts, Oct 26 2011

Status

approved