A393395 Number of permutations of length n sortable by a (2,2)-stack.

1, 1, 2, 6, 24, 116, 628, 3636, 21956, 136428, 865700, 5583580, 36490740, 241105516, 1607891780, 10808452348, 73159943124, 498215170508, 3411058716964, 23465785541468, 162121010290996, 1124393414877996, 7825541946451972, 54637557152397884, 382586828736801940, 2686126809776641932

Offset

0,3

Comments

A (2,2)-stack allows pushing into either of the top two positions and popping from either of the top two positions.

This class is defined by avoiding the permutations 23451, 23541, 32451, 32541, 245163, 246153, 425163, 426153.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

M. D. Atkinson, Generalized stack permutations, Combin. Probab. Comput. 7 (1998), no. 3, 239-246.

Formula

G.f. f(x) satisfies 2*x*f(x)^3 - (2*x+3)*f(x)^2 - (x-7)*f(x) - 4 = 0.

G.f.: 1 + Series_Reversion(x*(3*x - 1)/((x + 1)*(2*x^2 + 2*x - 1))). - Andrew Howroyd, Feb 18 2026

a(n) ~ sqrt(s*(1 + 2*s - 2*s^2) / (Pi*(3 + 2*r - 6*r*s))) / (2*n^(3/2) * r^(n - 1/2)), where r = (52 + sqrt(10531)*cos((2*Pi + arccos(1080647/10531^(3/2)))/3))/3 = 0.1338790671510627252896614474332139209739178... and s = (8 + sqrt(94)*cos((4*Pi + arccos(-191*sqrt(2/47)/47))/3))/9 = 1.2393827937375600536930234428899841975948603... - Vaclav Kotesovec, Feb 18 2026

Prog

(PARI) seq(n)={Vec(1 + serreverse(x*(3*x - 1)/((x + 1)*(2*x^2 + 2*x - 1)) + O(x*x^n)))} \\ Andrew Howroyd, Feb 18 2026

Crossrefs

Sequence in context: A242820 A228395 A082631 * A212198 A182216 A097483

Adjacent sequences: A393392 A393393 A393394 * A393396 A393397 A393398

Keyword

nonn

Author

Vincent Vatter, Feb 17 2026

Status

approved