login
Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb <--> bac <--> cba, where a<b<c.
1

%I #48 Feb 25 2024 04:28:10

%S 1,1,2,3,13,71,470,3497,29203,271500,2786711,31322803,382794114,

%T 5054810585,71735226535,1088920362030,17607174571553,302143065676513,

%U 5484510055766118,104999034898520903,2114467256458136473,44682676397748896010,988663144904696100347

%N Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb <--> bac <--> cba, where a<b<c.

%H Alois P. Heinz, <a href="/A212433/b212433.txt">Table of n, a(n) for n = 0..450</a>

%H Anders Claesson, <a href="https://akc.is/papers/036-From-Hertzsprungs-problem-to-pattern-rewriting-systems.pdf">From Hertzsprung's problem to pattern-rewriting systems</a>, University of Iceland (2020).

%H S. Linton, J. Propp, T. Roby, and J. West, <a href="http://arxiv.org/abs/1111.3920">Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions</a>, arXiv:1111.3920, 2011 [math.CO]

%F G.f.: Sum_{k>=0} k! * ( x * ((1-x^2)^2/(1-x^3) - x^2) )^k. - _Seiichi Manyama_, Feb 25 2024

%e From _Alois P. Heinz_, Jun 23 2012: (Start)

%e a(3) = 3: {123, 132, 213, 321}, {231}, {312}.

%e a(4) = 13: {1234, 1243, 1324, 1432, 2134, 3214}, {1342}, {1423}, {2143}, {2314}, {2341, 2431, 3241, 4123, 4132, 4213, 4321}, {2413}, {3124}, {3142}, {3412}, {3421}, {4231}, {4312}.

%e a(5) = 71: {12345, 12354, 12435, 12543, 13245, 13254, 14325, 21345, 21354, 21435, 21543, 32145, 32154}, {12453}, ..., {53412}, {53421}, {54231}.

%e (End)

%o (PARI) my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, k!*(x*((1-x^2)^2/(1-x^3)-x^2))^k)) \\ _Seiichi Manyama_, Feb 25 2024

%Y Cf. A212432, A212580, A212581.

%K nonn

%O 0,3

%A _Tom Roby_, Jun 21 2012

%E a(8)-a(9) from _Alois P. Heinz_, Jun 23 2012

%E a(10)-a(22) from _Alois P. Heinz_, Apr 14 2021