login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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