|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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!.
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
|
Columns k=0-10 give: A052186, A225960, A225963, A225964, A225965, A225966, A225967, A225968, A225969, A225970, A225971. - Alois P. Heinz, May 22 2013
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
