A186374 Number of strong fixed blocks in all the permutations of [n] (see first comment for definition).

0, 1, 1, 3, 11, 48, 248, 1500, 10476, 83328, 745344, 7413120, 81187200, 970928640, 12589240320, 175900757760, 2634526944000, 42103369728000, 715107004416000, 12862666543104000, 244249409359872000, 4882687056543744000, 102496533840691200000

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

Cf. A186373, A003149.

Sequence in context: A317170 A127087 A113060 * A187249 A105151 A111680

Adjacent sequences: A186371 A186372 A186373 * A186375 A186376 A186377

Keyword

nonn

Author

Emeric Deutsch, Apr 18 2011

Extensions

a(11)-a(22) from Alois P. Heinz, May 22 2013

Status

approved