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,4

Links

Alois P. Heinz, Rows n = 1..100, flattened

D. W. Wilson, Extended tables for A008304 and A064315

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

Crossrefs

Row sums give: A000142.

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

Cf. A030662, A064316.

Sequence in context: A222061 A378981 A345453 * A371994 A227322 A216718

Adjacent sequences: A064312 A064313 A064314 * A064316 A064317 A064318

Keyword

nonn,tabl

Author

David W. Wilson, Sep 07 2001

Status

approved