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

%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