A165522 -id:A165522 - cp's OEIS frontend

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

Vincent Vatter, Sep 21 2009

nonn

			For n=6, there are 394 separable permutations; 243 of them avoid 4321.

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).

Cf. A034943, A165522, A165523.

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

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

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

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.

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

A165523 The number of 654321-avoiding separable permutations of length n.

Original entry on oeis.org

1, 1, 2, 6, 22, 90, 393, 1769, 7957, 35133, 151675, 642695, 2689411, 11176469, 46313531, 191837707, 795251170, 3300506324, 13712825121, 57019988099, 237221971144, 987206194720, 4108816936769, 17101813661923, 71181293634767

Offset: 0

Vincent Vatter, Sep 25 2009

nonn

			For n=6, there are 394 separable permutations; all but one of them (654321 itself) avoid 654321, so a(6)=393.

G. C. Greubel, Table of n, a(n) for n = 0..1000
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 (37, -656, 7434, -60594, 378989, -1894854, 7789502, -26875022, 79043750, -200616320, 443695596, -861927311, 1480312985, -2259800395, 3079970285, -3761486169, 4128383734, -4081387760, 3640807867, -2934146785, 2137896384, -1408787953, 839470131, -452088473, 219815232, -96347460, 37986829, -13432485, 4243006, -1190714, 294604, -63561, 11762, -1818, 224, -20, 1).

Cf. A034943, A165521, A165522.

G.f.: ((x^7 - 4*x^6 + 12*x^5 - 23*x^4 + 28*x^3 - 19*x^2 + 7*x - 1)*(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^3 - 2*x^2 + 3*x - 1)^2*(x - 1)^5) / (1 + 63561*x^32 - 294604*x^31 - 378989*x^5 + 656*x^2 - 37*x - 224*x^35 - x^37 + 20*x^36 - 11762*x^33 + 1818*x^34 + 60594*x^4 + 2259800395*x^14 + 13432485*x^28 - 4243006*x^29 - 37986829*x^27 - 1480312985*x^13 + 1190714*x^30 + 3761486169*x^16 - 4128383734*x^17 + 4081387760*x^18 - 7789502*x^7 + 1894854*x^6 - 79043750*x^9 - 7434*x^3 + 200616320*x^10 - 3079970285*x^15 - 3640807867*x^19 + 2934146785*x^20 + 861927311*x^12 - 443695596*x^11 + 26875022*x^8 + 452088473*x^24 + 96347460*x^26 - 839470131*x^23 - 219815232*x^25 - 2137896384*x^21 + 1408787953*x^22). The growth rate (limit of the n-th root of a(n)) is approximately 4.16229.

a(0)=1 prepended by Alois P. Heinz, Dec 09 2015

cp's OEIS Frontend

A165521 The number of 4321-avoiding separable permutations of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions