|
|
A165328
|
|
The number of even separable permutations of length n
|
|
0
|
|
|
1, 1, 3, 12, 48, 197, 903, 4298, 20862, 103049, 518859, 2647296, 13651092, 71039373, 372693519, 1968822294, 10463661690, 55909013009, 300159426963, 1618362990804, 8759313066840, 47574827600981, 259215937709463
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
For n congruent to 2 or 3 mod 4, these are the little Schroeder numbers A001003, because the separable permutations are closed under reversal, and for these values of n, reversing the permutation corresponds to multiplying by an odd permutation. Thus for these values of n, precisely half of the separable permutations are even. For other values of n, it appears that strictly more than half of the separable permutations are even.
|
|
LINKS
|
|
|
FORMULA
|
G.f. f satisfies 4096*f^12 + (- 24576 + 24576*x)*f^11 + (- 116736*x + 65536 + 65536*x^2)*f^10 + (- 102400 + 235520*x + 102400*x^3 - 235520*x^2)*f^9 + (104000*x^4 - 259584*x + 327040*x^2 + 103744 - 259584*x^3)*f^8 + (163072*x - 70912 - 196096*x^2 + 196096*x^3 + 71936*x^5 - 164096*x^4)*f^7 + (34464*x^6 - 52288*x^5 + 27520*x^3 + 5600*x^2 - 48704*x + 7296*x^4 + 32640)*f^6 + (- 5952*x + 63776*x^2 + 480*x^6 - 9472 - 58688*x^5 + 11360*x^7 - 115040*x^3 + 113536*x^4)*f^5 + (7312*x^7 - 34528*x^6 + 2484*x^8 + 59440*x^3 - 40248*x^2 + 56496*x^5 - 63284*x^4 + 1272 + 11792*x)*f^4 +
+ (- 7344*x^3 + 10800*x^2 - 4848*x - 472*x^4 + 328*x^9 + 2904*x^8 + 152*x^5 + 6656*x^6 - 8320*x^7 + 144)*f^3 + (- 429*x^2 + 882*x + 528*x^9 - 554*x^8 - 2632*x^7 + 20*x^10 - 11750*x^5 + 10471*x^4 - 4484*x^3 + 8045*x^6 - 81)*f^2 + (40*x^10 + 122*x^9 + 9 + 1961*x^7 - 3087*x^6 + 4129*x^5 - 874*x^8 + 2247*x^3 - 513*x^2 - 27*x - 4007*x^4)*f - 351*x^3 - 9*x + 99*x^2 + 615*x^4 - 78*x^9 - 603*x^5 + 361*x^6 - 183*x^7 + 130*x^8 + 20*x^10 = 0.
|
|
EXAMPLE
|
For n=4 there are 22 separable permutations, and 12 of these are even. Thus a(4)=12.
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|