|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|