A212419 Size of the equivalence class of S_n containing the identity permutation under transformations of positionally adjacent elements of the form abc <--> acb <--> bac <--> cba, where a

1, 1, 1, 4, 21, 116, 713, 5030, 40301, 362852, 3628744, 39916716, 479001426, 6227020536, 87178290639, 1307674367142, 20922789886141, 355687428093140, 6402373705721708, 121645100408822276, 2432902008176618342, 51090942171709406408, 1124000727777607604418

Offset: 0

Author

Tom Roby, May 15 2012

Keywords

• nonn
• easy

Comments

Pierrot, Rossin, and West were first to give a formula and the alternate characterization: all permutations in S_n except the alternating permutations in which the elements in odd positions form a decreasing sequence, and the elements in even positions also form a decreasing sequence.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..449
• Steven Linton, James Propp, Tom Roby, and Julian West, Equivalence classes of permutations under various relations generated by constrained transpositions, 2011 arXiv:1111.3920 [math.CO], 2011; J. Int. Seq. 15 (2012) #12.9.1.
• A. Pierrot, D. Rossin, and J. West, Adjacent transformations in permutations, FPSAC 2011, Discrete Math. Theor. Comput. Sci. Proc., 2011.

Crossrefs

Cf. A000108.

Programs

Maple

C:= n-> binomial(2*n, n)/(n+1):
a:= n-> `if`(n<3, 1, n!-C(floor((n-1)/2))-C(floor(n/2))):
seq (a(n), n=0..30);  # Alois P. Heinz, May 20 2012

Mathematica

Join[{1,1,1},Table[n!-CatalanNumber[Floor[(n-1)/2]]-CatalanNumber[ Floor[ n/2]],{n,3,30}]] (* Harvey P. Dale, Dec 31 2013 *)

Formula

a(n) = 1 for n<3, otherwise: a(n) = n!-C([(n-1)/2])-C([n/2]), where [x] is the floor function and C(n) denotes the n-th Catalan number (A000108).