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

1, 1, 2, 4, 17, 89, 556, 4011, 32843, 301210, 3059625, 34104275, 413919214, 5434093341, 76734218273, 1159776006262, 18681894258591, 319512224705645, 5782488507020050, 110407313135273127, 2218005876646727423, 46767874983437110354, 1032732727339665789981

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, 2011 arXiv:1111.3920 [math.CO] J. Int. Seq. 15 (2012) #12.9.1

Formula

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

Example

From Alois P. Heinz, May 22 2012: (Start)
a(3) = 4: {123, 132, 213}, {231}, {312}, {321}.
a(4) = 17: {1234, 1243, 1324, 2134}, {1342}, {1423}, {1432}, {2143}, {2314}, {2341, 2431, 3241}, {2413}, {3124}, {3142}, {3214}, {3412}, {3421}, {4123, 4132, 4213}, {4231}, {4312}, {4321}. (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))^k)) \\ Seiichi Manyama, Feb 20 2024

Crossrefs

Cf. A210667, A210668, A210669, A210671, A212417, A212580.

Sequence in context: A014522 A020035 A112005 * A305786 A009319 A347724

Adjacent sequences: A212578 A212579 A212580 * A212582 A212583 A212584

Keyword

nonn

Author

Tom Roby, May 21 2012

Extensions

a(9) from Alois P. Heinz, May 22 2012

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

Status

approved