|
%I #49 Apr 22 2022 09:02:12
%S 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,
%T 1,36287,3853,110,69,0,0,0,1,333395,27555,1679,250,0,0,0,0,1,3382758,
%U 233431,11941,418,251,0,0,0,0,1,37688597,2167152,59470,658,922,0,0,0,0,0,1
%N Triangle of number of permutations by length of shortest ascending run.
%H Alois P. Heinz, <a href="/A064315/b064315.txt">Rows n = 1..100, flattened</a>
%H D. W. Wilson, <a href="/A008304/a008304.txt">Extended tables for A008304 and A064315</a>
%F T(2*n,n) = binomial(2*n,n)-1 = A030662(n).
%F Sum_{k=1..n} k * T(n,k) = A064316(n).
%e 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.
%e Triangle T(n,k) begins:
%e 1;
%e 1, 1;
%e 5, 0, 1;
%e 18, 5, 0, 1;
%e 101, 18, 0, 0, 1;
%e 611, 89, 19, 0, 0, 1;
%e 4452, 519, 68, 0, 0, 0, 1,
%e 36287, 3853, 110, 69, 0, 0, 0, 1;
%e ...
%p A:= proc(n, k) option remember; local b; b:=
%p proc(u, o, t) option remember; `if`(t+o<=k, (u+o)!,
%p add(b(u+i-1, o-i, min(k, t)+1), i=1..o)+
%p `if`(t<=k, u*(u+o-1)!, add(b(u-i, o+i-1, 1), i=1..u)))
%p end: forget(b):
%p add(b(j-1, n-j, 1), j=1..n)
%p end:
%p T:= (n, k)-> A(n, k) -A(n, k-1):
%p seq(seq(T(n, k), k=1..n), n=1..12); # _Alois P. Heinz_, Aug 29 2013
%t 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_ *)
%Y Row sums give: A000142.
%Y Columns k=1-10 give: A228614, A185652, A228670, A228671, A228672, A228673, A228674, A228675, A228676, A228677.
%Y Cf. A030662, A064316.
%K nonn,tabl
%O 1,4
%A _David W. Wilson_, Sep 07 2001
|
