login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #24 Jan 08 2013 18:08:24

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

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

%C 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.

%D James Pfeiffer, personal communication.

%H Dominique Foata and Marcel-Paul Schützenberger, <a href="http://dx.doi.org/10.1002/mana.19780830111">Major Index and inversion number of permutations</a>, Math. Nachr. 83 (1978), 143-159

%e The orbits of S_4 are:

%e [(1, 2, 3, 4)]

%e [(2, 1, 3, 4)]

%e [(2, 3, 1, 4)]

%e [(2, 3, 4, 1)]

%e [(3, 2, 1, 4)]

%e [(3, 2, 4, 1)]

%e [(3, 4, 2, 1)]

%e [(4, 3, 2, 1)]

%e [(2, 1, 4, 3), (4, 2, 1, 3), (2, 4, 1, 3)]

%e [(2, 4, 3, 1), (4, 2, 3, 1)]

%e [(1, 3, 2, 4), (3, 1, 2, 4)]

%e [(1, 3, 4, 2), (3, 1, 4, 2), (3, 4, 1, 2)]

%e [(1, 4, 3, 2), (4, 3, 1, 2)]

%e [(4, 1, 3, 2)]

%e [(1, 2, 4, 3), (4, 1, 2, 3)]

%e [(1, 4, 2, 3)]

%Y Cf. A195931, A195924, A065161

%K nonn,hard,more

%O 0,3

%A _Austin Roberts_, Oct 26 2011