A195924 The number of fixed points in S_n by the action of Foata's bijection.

1, 1, 2, 4, 10, 26, 80, 256, 918, 3464

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

Below are the orbits of S_4 in order of size. The first 10 are fixed points.
[(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)]
[(4, 1, 3, 2)]
[(1, 4, 2, 3)]
[(2, 4, 3, 1), (4, 2, 3, 1)]
[(1, 3, 2, 4), (3, 1, 2, 4)]
[(1, 4, 3, 2), (4, 3, 1, 2)]
[(1, 2, 4, 3), (4, 1, 2, 3)]
[(2, 1, 4, 3), (4, 2, 1, 3), (2, 4, 1, 3)]
[(1, 3, 4, 2), (3, 1, 4, 2), (3, 4, 1, 2)]

Crossrefs

Cf. A195924, A195931, A065161.

Sequence in context: A179381 A096807 A003239 * A116673 A135410 A148103

Adjacent sequences: A195921 A195922 A195923 * A195925 A195926 A195927

Keyword

nonn,hard,more

Author

Austin Roberts Oct 26 2011

Status

approved