A165521 -id:A165521 - cp's OEIS frontend

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

1, 1, 2, 6, 22, 89, 368, 1488, 5831, 22311, 84223, 316181, 1185884, 4452567, 16742230, 63025805, 237423928, 894681874, 3371727204, 12706639594, 47884046357, 180440982667, 679939553548, 2562134671440, 9654584875285, 36380338185856, 137088669193146

Offset: 0

Vincent Vatter, Sep 21 2009

			For n=6, there are 394 separable permutations; 368 of them avoid 54321.

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 (18, -148, 743, -2564, 6488, -12536, 18999, -22992, 22474, -17876, 11622, -6189, 2697, -957, 273, -61, 10, -1).

Cf. A034943, A165521, A165523.

m:=50; R:=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

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

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

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]

The growth rate (limit of the n-th root of a(n)) is approximately 3.76823.

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula