cp's OEIS Frontend

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

%I A165522 #18 Sep 08 2022 08:45:47
%S A165522 1,1,2,6,22,89,368,1488,5831,22311,84223,316181,1185884,4452567,
%T A165522 16742230,63025805,237423928,894681874,3371727204,12706639594,
%U A165522 47884046357,180440982667,679939553548,2562134671440,9654584875285,36380338185856,137088669193146
%N A165522 The number of 54321-avoiding separable permutations of length n.
%H A165522 G. C. Greubel, <a href="/A165522/b165522.txt">Table of n, a(n) for n = 0..1000</a>
%H A165522 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 A165522 <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 A165522 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 A165522 The growth rate (limit of the n-th root of a(n)) is approximately 3.76823.
%e A165522 For n=6, there are 394 separable permutations; 368 of them avoid 54321.
%t A165522 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 A165522 (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 A165522 (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 A165522 Cf. A034943, A165521, A165523.
%K A165522 nonn,easy
%O A165522 0,3
%A A165522 _Vincent Vatter_, Sep 21 2009