|
| |
|
|
A165523
|
|
The number of 654321-avoiding separable permutations of length n.
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
LINKS
|
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.
|
|
|
EXAMPLE
|
For n=6, there are 394 separable permutations; all but one of them (654321 itself) avoid 654321, so a(6)=393.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
