A195924 -id:A195924 - cp's OEIS frontend

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

Austin Roberts, Oct 26 2011

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.

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

James Pfeiffer, personal communication.

Dominique Foata and Marcel-Paul Schützenberger, Major Index and inversion number of permutations, Math. Nachr. 83 (1978), 143-159

Cf. A195931, A195924, A065161

A207018 Number of permutations in S_n with major index equal to inversion number.

Original entry on oeis.org

1, 2, 4, 10, 28, 116, 576, 3634, 26620, 223440, 2100964, 21888712, 250062982, 3108430640

Offset: 1

William J. Keith, Feb 14 2012

At first equal to and eventually greater than corresponding entry of A195924, number of fixed points of Foata's bijection.

For any large n, the two permutations with maj and inv both 2 are 2314..n, and 14235..n.

			A(4)=10: the 10 permutations of 4 elements with major index equal to inversion number are
   #:       perm      #inv.   inversion table
   1:    [ 0 1 2 3 ]   0    [ 0 0 0 ]
   2:    [ 0 3 1 2 ]   2    [ 0 2 0 ]
   3:    [ 1 0 2 3 ]   1    [ 0 0 1 ]
   4:    [ 1 2 0 3 ]   2    [ 0 1 1 ]
   5:    [ 1 2 3 0 ]   3    [ 1 1 1 ]
   6:    [ 2 1 0 3 ]   3    [ 0 1 2 ]
   7:    [ 2 1 3 0 ]   4    [ 1 1 2 ]
   8:    [ 2 3 1 0 ]   5    [ 1 2 2 ]
   9:    [ 3 0 2 1 ]   4    [ 1 0 3 ]
  10:    [ 3 2 1 0 ]   6    [ 1 2 3 ]

Joerg Arndt, C++ program to compute terms.

Cf. A195924.

a(14) by Joerg Arndt, Sep 29 2012.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs