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

Author

Emeric Deutsch, Apr 18 2011

Keywords

• nonn

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.

Examples

			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).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..450

Crossrefs

Cf. A186373, A003149.

Programs

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 *)

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

Extensions

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