A165523 The number of 654321-avoiding separable permutations of length n.
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
Keywords
Examples
For n=6, there are 394 separable permutations; all but one of them (654321 itself) avoid 654321, so a(6)=393.
Links
- 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).
Formula
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.
Extensions
a(0)=1 prepended by Alois P. Heinz, Dec 09 2015