cp's OEIS Frontend

A064315 Triangle of number of permutations by length of shortest ascending run.

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