|
%I #25 Aug 13 2020 22:15:27
%S 1,1,1,4,21,116,713,5030,40301,362852,3628744,39916716,479001426,
%T 6227020536,87178290639,1307674367142,20922789886141,355687428093140,
%U 6402373705721708,121645100408822276,2432902008176618342,51090942171709406408,1124000727777607604418
%N 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<b<c.
%C 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.
%H Alois P. Heinz, <a href="/A212419/b212419.txt">Table of n, a(n) for n = 0..449</a>
%H Steven Linton, James Propp, Tom Roby, and Julian West, <a href="http://arxiv.org/abs/1111.3920">Equivalence classes of permutations under various relations generated by constrained transpositions, 2011</a> arXiv:1111.3920 [math.CO], 2011; <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Roby/roby4.html">J. Int. Seq. 15 (2012) #12.9.1</a>.
%H A. Pierrot, D. Rossin, and J. West, <a href="https://dmtcs.episciences.org/2951">Adjacent transformations in permutations</a>, FPSAC 2011, Discrete Math. Theor. Comput. Sci. Proc., 2011.
%F 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).
%p C:= n-> binomial(2*n, n)/(n+1):
%p a:= n-> `if`(n<3, 1, n!-C(floor((n-1)/2))-C(floor(n/2))):
%p seq (a(n), n=0..30); # _Alois P. Heinz_, May 20 2012
%t Join[{1,1,1},Table[n!-CatalanNumber[Floor[(n-1)/2]]-CatalanNumber[ Floor[ n/2]],{n,3,30}]] (* _Harvey P. Dale_, Dec 31 2013 *)
%Y Cf. A000108.
%K nonn
%O 0,4
%A _Tom Roby_, May 15 2012
|
