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,6

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

Links

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

Example

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;

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

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

Sequence in context: A288137 A287501 A287537 * A063550 A367672 A298960

Adjacent sequences: A186370 A186371 A186372 * A186374 A186375 A186376

Keyword

nonn,tabf

Author

Emeric Deutsch, Apr 18 2011

Extensions

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

Status

approved