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

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

Offset: 1

Author

David W. Wilson, Sep 07 2001

Keywords

• nonn
• tabl

Examples

			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;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..100, flattened
• D. W. Wilson, Extended tables for A008304 and A064315

Crossrefs

Row sums give: A000142.

Columns k=1-10 give: A228614, A185652, A228670, A228671, A228672, A228673, A228674, A228675, A228676, A228677.

Cf. A030662, A064316.

Programs

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):
seq(seq(T(n, k), k=1..n), n=1..12); # Alois P. Heinz, Aug 29 2013

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 *)

Formula

T(2*n,n) = binomial(2*n,n)-1 = A030662(n).

Sum_{k=1..n} k * T(n,k) = A064316(n).