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

Author

Vincent Vatter, Sep 21 2009

Keywords

• nonn
• easy

Examples

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

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).

Crossrefs

Cf. A034943, A165521, A165523.

Programs

Magma

m:=50; R:=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

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 *)

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

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.