A212433 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, 1, 2, 3, 13, 71, 470, 3497, 29203, 271500, 2786711, 31322803, 382794114, 5054810585, 71735226535, 1088920362030, 17607174571553, 302143065676513, 5484510055766118, 104999034898520903, 2114467256458136473, 44682676397748896010, 988663144904696100347

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..450

Anders Claesson, From Hertzsprung's problem to pattern-rewriting systems, University of Iceland (2020).

S. Linton, J. Propp, T. Roby, and J. West, Equivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions, arXiv:1111.3920, 2011 [math.CO]

Formula

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

Example

From Alois P. Heinz, Jun 23 2012: (Start)
a(3) = 3: {123, 132, 213, 321}, {231}, {312}.
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}.
a(5) = 71: {12345, 12354, 12435, 12543, 13245, 13254, 14325, 21345, 21354, 21435, 21543, 32145, 32154}, {12453}, ..., {53412}, {53421}, {54231}.
(End)

Prog

(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

Crossrefs

Cf. A212432, A212580, A212581.

Sequence in context: A219698 A293251 A061912 * A013167 A224239 A361520

Adjacent sequences: A212430 A212431 A212432 * A212434 A212435 A212436

Keyword

nonn

Author

Tom Roby, Jun 21 2012

Extensions

a(8)-a(9) from Alois P. Heinz, Jun 23 2012

a(10)-a(22) from Alois P. Heinz, Apr 14 2021

Status

approved