login
A165521
The number of 4321-avoiding separable permutations of length n.
3
1, 1, 2, 6, 21, 73, 243, 785, 2504, 7968, 25389, 81033, 258873, 827263, 2643616, 8447300, 26990489, 86236655, 275531223, 880341121, 2812760102, 8987010878, 28714292671, 91744697633, 293132350135, 936583428475, 2992465580300
OFFSET
0,3
LINKS
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 2 No 102.
V. Vatter, Finding regular insertion encodings for permutation classes, Journal of Symbolic Computation, Volume 47, Issue 3, March 2012, Pages 259-265.
FORMULA
G.f.: (1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7).
The growth rate (limit of the n-th root of a(n)) is approximately 3.19508.
EXAMPLE
For n=6, there are 394 separable permutations; 243 of them avoid 4321.
MATHEMATICA
CoefficientList[Series[(1 - x)^3*(1 -3*x +2*x^2 -x^3)/(1 -7*x +19*x^2 - 28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7), {x, 0, 50}], x] (* G. C. Greubel, Oct 21 2018 *)
PROG
(PARI) x='x+O('x^50); Vec((1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7)) \\ G. C. Greubel, Oct 21 2018
(Magma) m:=50; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x)^3*(1 -3*x +2*x^2 -x^3)/ (1 -7*x +19*x^2 -28*x^3 +23*x^4 -12*x^5 +4*x^6 -x^7))); // G. C. Greubel, Oct 21 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Vincent Vatter, Sep 21 2009
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015
STATUS
approved