A165522 The number of 54321-avoiding separable permutations of length n.

1, 1, 2, 6, 22, 89, 368, 1488, 5831, 22311, 84223, 316181, 1185884, 4452567, 16742230, 63025805, 237423928, 894681874, 3371727204, 12706639594, 47884046357, 180440982667, 679939553548, 2562134671440, 9654584875285, 36380338185856, 137088669193146

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.

Index entries for linear recurrences with constant coefficients, signature (18, -148, 743, -2564, 6488, -12536, 18999, -22992, 22474, -17876, 11622, -6189, 2697, -957, 273, -61, 10, -1).

Formula

G.f.: (1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3+23*x^4 -12*x^5 +4*x^6-x^7) / (x^18 -10*x^17 +61*x^16 -273*x^15 +957*x^14 -2697*x^13 +6189*x^12 -11622*x^11 +17876*x^10 -22474*x^9 +22992*x^8 -18999*x^7 +12536*x^6 -6488*x^5 +2564*x^4 -743*x^3 +148*x^2 -18*x +1). [typo fixed by Colin Barker, Jul 05 2013]

The growth rate (limit of the n-th root of a(n)) is approximately 3.76823.

Example

For n=6, there are 394 separable permutations; 368 of them avoid 54321.

Mathematica

CoefficientList[Series[(1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3 + 23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16-273*x^15+957*x^14- 2697*x^13+6189*x^12-11622*x^11+17876*x^10-22474*x^9+22992*x^8-18999*x^7 +12536*x^6-6488*x^5+2564*x^4-743*x^3+148*x^2-18*x+1), {x, 0, 50}], x] (* G. C. Greubel, Oct 21 2018 *)

Prog

(PARI) x='x+O('x^50); Vec((1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2 -28*x^3+23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16 -273*x^15 +957*x^14 -2697*x^13+6189*x^12-11622*x^11+17876*x^10-22474*x^9 +22992*x^8 -18999*x^7+12536*x^6-6488*x^5+2564*x^4-743*x^3+148*x^2 -18*x+1)) \\ G. C. Greubel, Oct 21 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)^4*(1-3*x+2*x^2-x^3)^2*(1-7*x+19*x^2-28*x^3 + 23*x^4-12*x^5+4*x^6-x^7)/(x^18-10*x^17+61*x^16-273*x^15+957*x^14- 2697*x^13+6189*x^12 -11622*x^11+17876*x^10-22474*x^9+22992*x^8-18999*x^7 +12536*x^6-6488*x^5 +2564*x^4-743*x^3+148*x^2-18*x+1))); // G. C. Greubel, Oct 21 2018

Crossrefs

Cf. A034943, A165521, A165523.

Sequence in context: A107944 A150265 A150266 * A150267 A271388 A165540

Adjacent sequences: A165519 A165520 A165521 * A165523 A165524 A165525

Keyword

nonn,easy

Author

Vincent Vatter, Sep 21 2009

Status

approved