%I #38 Nov 25 2019 01:00:01
%S 1,0,1,1,1,3,3,14,9,1,77,38,5,497,198,25,3676,1229,134,1,30677,8819,
%T 815,9,285335,71825,5657,63,2928846,654985,44549,419,1,32903721,
%U 6615932,394266,2868,13,401739797,73357572,3883182,20932,117,5298600772,886078937,42174500,165662,928,1
%N Triangle read by rows: T(n,k) is the number of permutations of [n] having k strong fixed blocks (see first comment for definition).
%C 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.
%C Apparently, row n has 1+ceiling(n/3) entries.
%C Sum of entries in row n is n!.
%C T(n,0) = A052186(n).
%C Sum_{k>=0} k*T(n,k) = A186374(n).
%C Entries obtained by direct counting (via Maple).
%C In general, column k > 1 is asymptotic to (k-1) * n! / n^(3*k-4). - _Vaclav Kotesovec_, Aug 29 2014
%H Alois P. Heinz, <a href="/A186373/b186373.txt">Rows n = 0..200, flattened</a>
%e T(3,1) = 3 because we have [123], [1]32, and 21[3] (the strong fixed blocks are shown between square brackets).
%e T(7,3) = 1 because we have [1]32[4]65[7] (the strong fixed blocks are shown between square brackets).
%e Triangle starts:
%e 1;
%e 0, 1;
%e 1, 1;
%e 3, 3;
%e 14, 9, 1;
%e 77, 38, 5;
%e 497, 198, 25;
%e 3676, 1229, 134, 1;
%e 30677, 8819, 815, 9;
%e 285335, 71825, 5657, 63;
%e 2928846, 654985, 44549, 419, 1;
%p b:= proc(n) b(n):=-`if`(n<0, 1, add(b(n-i-1)*i!, i=0..n)) end:
%p f:= proc(n) f(n):=`if`(n<=0, 0, b(n-1)+f(n-1)) end:
%p B:= proc(n, k) option remember; `if`(k=0, 0, `if`(k=1, f(n),
%p add((f(n-i)-1)*B(i,k-1), i=3*k-5..n-3)))
%p end:
%p T:= proc(n, k) option remember; `if`(k=0, b(n),
%p add(b(n-i)*B(i, k), i=3*k-2..n))
%p end:
%p seq(seq(T(n, k), k=0..ceil(n/3)), n=0..20); # _Alois P. Heinz_, May 23 2013
%t 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_ *)
%Y Cf. A000142, A186374, A052186, A145878.
%Y Columns k=0-10 give: A052186, A225960, A225963, A225964, A225965, A225966, A225967, A225968, A225969, A225970, A225971. - _Alois P. Heinz_, May 22 2013
%K nonn,tabf
%O 0,6
%A _Emeric Deutsch_, Apr 18 2011
%E Rows n=11-13 (16 terms) from _Alois P. Heinz_, May 22 2013