A185652 -id:A185652 - cp's OEIS frontend

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

David W. Wilson, Sep 07 2001

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

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

Row sums give: A000142.
Columns k=1-10 give: A228614, A185652, A228670, A228671, A228672, A228673, A228674, A228675, A228676, A228677.
Cf. A030662, A064316.

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

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

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

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

A186735 Number of permutations of [n] with no ascending runs of length 1 or 2.

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 20, 69, 180, 1930, 12611, 61051, 566129, 5179750, 38348469, 376547340, 4169246332, 41559058969, 465750294781, 5905176350849, 72848728572828, 946103621115633, 13501160406995728, 195518567272213262, 2918439778172724571, 46559546190633191495

Offset: 0

Alois P. Heinz, Aug 29 2013

nonn

			a(0) = 1: the empty permutation.
a(3) = 1: 123.
a(4) = 1: 1234.
a(5) = 1: 12345.
a(6) = 20: 123456, 124356, 125346, 126345, 134256, 135246, 136245, 145236, 146235, 156234, 234156, 235146, 236145, 245136, 246135, 256134, 345126, 346125, 356124, 456123.

Alois P. Heinz, Table of n, a(n) for n = 0..150

Cf. A064315, A097899.

Cf. A000142, A185652, A228614.

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}]];
a[n_] := n! - A[n, 2];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Sep 03 2021, after Alois P. Heinz in A064315 *)

a(n) = A000142(n) - A228614(n) - A185652(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula