|
|
A186374
|
|
Number of strong fixed blocks in all the permutations of [n] (see first comment for definition).
|
|
2
|
|
|
0, 1, 1, 3, 11, 48, 248, 1500, 10476, 83328, 745344, 7413120, 81187200, 970928640, 12589240320, 175900757760, 2634526944000, 42103369728000, 715107004416000, 12862666543104000, 244249409359872000, 4882687056543744000, 102496533840691200000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A fixed block of a permutation p is a maximal sequence of consecutive fixed points of p. For example, the permutation 213486759 has 3 fixed blocks: 34, 67, and 9. A fixed block f of a permutation p is said to be strong if all the entries to the left (right) of f are smaller (larger) than all the entries of f. In the above example, only 34 and 9 are strong fixed blocks.
|
|
LINKS
|
|
|
FORMULA
|
Apparently, a(n) = A003149(n-1)-A003149(n-2) or, equivalently, a(n)=(n-1)! + Sum(k!*(n-2-k)!*(n-2-k), k=0..n-2).
a(n) ~ 2 * (n-1)! * ((1 + 1/n^2 + 7/n^3 + 49/n^4 + 391/n^5 + 3601/n^6 + 37927/n^7 + 451249/n^8 + 5995591/n^9 + 88073041/n^10)). - Vaclav Kotesovec, Mar 17 2015
Recurrence (for n>=3): 2*(n^2 - 7*n + 11)*a(n) = (n-2)*(3*n^2 - 17*n + 17)*a(n-1) - (n-2)^2*(n^2 - 5*n + 5)*a(n-2). - Vaclav Kotesovec, Aug 04 2015
|
|
EXAMPLE
|
a(3) = 3 because in [123], [1]32, 21[3], 231, 312, 321 we have 1 + 1 + 1 + 0 + 0 + 0 strong fixed blocks (shown between square brackets).
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n<5, [0, 1, 1, 3, 11][n+1],
((3*n^2-12*n+2)*a(n-1) -(n^3-3*n^2-8*n+23)*a(n-2)
+(n-3)^3*a(n-3)) / (2*n-8))
end:
|
|
MATHEMATICA
|
Flatten[{0, 1, Table[(n-1)! + Sum[k!*(n-2-k)!*(n-2-k), {k, 0, n-2}], {n, 2, 20}]}] (* Vaclav Kotesovec, Aug 04 2015 *)
Flatten[{0, Simplify[Table[Gamma[n] * (1 - (n-2)*(I*Pi/2^n + LerchPhi[2, 1, n])), {n, 1, 20}]]}] (* Vaclav Kotesovec, Aug 04 2015 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|