A165521 The number of 4321-avoiding separable permutations of length n.
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
Keywords
Examples
For n=6, there are 394 separable permutations; 243 of them avoid 4321.
Links
- G. C. Greubel, Table of n, a(n) for n = 0..1000
- 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.
- Index entries for linear recurrences with constant coefficients, signature (7,-19,28,-23,12,-4,1).
Programs
-
Magma
m:=50; R
:=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 -
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 *) -
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
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.
Extensions
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015