A165522 - OEIS

%I #18 Sep 08 2022 08:45:47

%S 1,1,2,6,22,89,368,1488,5831,22311,84223,316181,1185884,4452567,

%T 16742230,63025805,237423928,894681874,3371727204,12706639594,

%U 47884046357,180440982667,679939553548,2562134671440,9654584875285,36380338185856,137088669193146

%N The number of 54321-avoiding separable permutations of length n.

%H G. C. Greubel, <a href="/A165522/b165522.txt">Table of n, a(n) for n = 0..1000</a>

%H V. Vatter, <a href="https://doi.org/10.1016/j.jsc.2011.11.002">Finding regular insertion encodings for permutation classes</a>, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.

%H <a href="/index/Rec#order_18">Index entries for linear recurrences with constant coefficients</a>, signature (18, -148, 743, -2564, 6488, -12536, 18999, -22992, 22474, -17876, 11622, -6189, 2697, -957, 273, -61, 10, -1).

%F 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]

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

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

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

%o (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

%o (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

%Y Cf. A034943, A165521, A165523.

%K nonn,easy

%O 0,3

%A _Vincent Vatter_, Sep 21 2009