|
|
A064315
|
|
Triangle of number of permutations by length of shortest ascending run.
|
|
14
|
|
|
1, 1, 1, 5, 0, 1, 18, 5, 0, 1, 101, 18, 0, 0, 1, 611, 89, 19, 0, 0, 1, 4452, 519, 68, 0, 0, 0, 1, 36287, 3853, 110, 69, 0, 0, 0, 1, 333395, 27555, 1679, 250, 0, 0, 0, 0, 1, 3382758, 233431, 11941, 418, 251, 0, 0, 0, 0, 1, 37688597, 2167152, 59470, 658, 922, 0, 0, 0, 0, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
LINKS
|
|
|
FORMULA
|
T(2*n,n) = binomial(2*n,n)-1 = A030662(n).
Sum_{k=1..n} k * T(n,k) = A064316(n).
|
|
EXAMPLE
|
Sequence (1, 3, 2, 5, 4) has ascending runs (1, 3), (2, 5), (4), the shortest is length 1. Of all permutations of (1, 2, 3, 4, 5), T(5,1) = 101 have shortest ascending run of length 1.
Triangle T(n,k) begins:
1;
1, 1;
5, 0, 1;
18, 5, 0, 1;
101, 18, 0, 0, 1;
611, 89, 19, 0, 0, 1;
4452, 519, 68, 0, 0, 0, 1,
36287, 3853, 110, 69, 0, 0, 0, 1;
...
|
|
MAPLE
|
A:= proc(n, k) option remember; local b; b:=
proc(u, o, t) option remember; `if`(t+o<=k, (u+o)!,
add(b(u+i-1, o-i, min(k, t)+1), i=1..o)+
`if`(t<=k, u*(u+o-1)!, add(b(u-i, o+i-1, 1), i=1..u)))
end: forget(b):
add(b(j-1, n-j, 1), j=1..n)
end:
T:= (n, k)-> A(n, k) -A(n, k-1):
|
|
MATHEMATICA
|
A[n_, k_] := A[n, k] = Module[{b}, b[u_, o_, t_] := b[u, o, t] = If[t+o <= k, (u+o)!, Sum[b[u+i-1, o-i, Min[k, t]+1], {i, 1, o}] + If[t <= k, u*(u+o-1)!, Sum[ b[u-i, o+i-1, 1], {i, 1, u}]]]; Sum[b[j-1, n-j, 1], {j, 1, n}]]; T[n_, k_] := A[n, k] - A[n, k-1]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|