A186373 Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed blocks (see first comment for definition).

1, 0, 1, 1, 1, 3, 3, 14, 9, 1, 77, 38, 5, 497, 198, 25, 3676, 1229, 134, 1, 30677, 8819, 815, 9, 285335, 71825, 5657, 63, 2928846, 654985, 44549, 419, 1, 32903721, 6615932, 394266, 2868, 13, 401739797, 73357572, 3883182, 20932, 117, 5298600772, 886078937, 42174500, 165662, 928, 1

Offset: 0

Author

Emeric Deutsch, Apr 18 2011

Keywords

• nonn
• tabf

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.

Apparently, row n has 1+ceiling(n/3) entries.

Sum of entries in row n is n!.

T(n,0) = A052186(n).

Sum_{k>=0} k*T(n,k) = A186374(n).

Entries obtained by direct counting (via Maple).

In general, column k > 1 is asymptotic to (k-1) * n! / n^(3*k-4). - Vaclav Kotesovec, Aug 29 2014

Examples

			T(3,1) = 3 because we have [123], [1]32, and 21[3] (the strong fixed blocks are shown between square brackets).
T(7,3) = 1 because we have [1]32[4]65[7] (the strong fixed blocks are shown between square brackets).
Triangle starts:
        1;
        0,      1;
        1,      1;
        3,      3;
       14,      9,     1;
       77,     38,     5;
      497,    198,    25;
     3676,   1229,   134,   1;
    30677,   8819,   815,   9;
   285335,  71825,  5657,  63;
  2928846, 654985, 44549, 419,  1;
		

Links

• Alois P. Heinz, Rows n = 0..200, flattened

Crossrefs

Cf. A000142, A186374, A052186, A145878.

Columns k=0-10 give: A052186, A225960, A225963, A225964, A225965, A225966, A225967, A225968, A225969, A225970, A225971. - Alois P. Heinz, May 22 2013

Programs

Maple

b:= proc(n) b(n):=-`if`(n<0, 1, add(b(n-i-1)*i!, i=0..n)) end:
f:= proc(n) f(n):=`if`(n<=0, 0, b(n-1)+f(n-1)) end:
B:= proc(n, k) option remember; `if`(k=0, 0, `if`(k=1, f(n),
      add((f(n-i)-1)*B(i,k-1), i=3*k-5..n-3)))
    end:
T:= proc(n, k) option remember; `if`(k=0, b(n),
      add(b(n-i)*B(i, k), i=3*k-2..n))
    end:
seq(seq(T(n, k), k=0..ceil(n/3)), n=0..20); # Alois P. Heinz, May 23 2013

Mathematica

b[n_] := b[n] = -If[n<0, 1, Sum[b[n-i-1]*i!, {i, 0, n}]]; f[n_] := f[n] = If[n <= 0, 0, b[n-1] + f[n-1]]; B[n_, k_] :=  B[n, k] = If[k == 0, 0, If[k == 1, f[n],  Sum[(f[n-i]-1)*B[i, k-1], {i, 3*k-5, n-3}]]]; T[n_, k_] := T[n, k] = If[k == 0, b[n], Sum[b[n-i]*B[i, k], {i, 3*k-2, n}]]; Table[Table[T[n, k], {k, 0, Ceiling[ n/3]}], {n, 0, 20}] // Flatten (* Jean-François Alcover, Feb 20 2015, after Alois P. Heinz *)

Extensions

Rows n=11-13 (16 terms) from Alois P. Heinz, May 22 2013