cp's OEIS Frontend

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

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