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
Alois P. Heinz, Table of n, a(n) for n = 0..450
FORMULA
a(n) = Sum(k*A186373(n,k), k>=0).
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:
seq(a(n), n=0..24); # Alois P. Heinz, May 22 2013
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
Emeric Deutsch, Apr 18 2011
EXTENSIONS
a(11)-a(22) from Alois P. Heinz, May 22 2013
STATUS
approved