A258690 Total number of longest increasing runs in all permutations of [n].

1, 1, 3, 8, 32, 167, 1096, 8117, 67859, 627649, 6394781, 71201812, 861677250, 11270215084, 158564826122, 2389093936957, 38396351412220, 655832914215010, 11865953978478454, 226724258401651143, 4562163514498852598, 96430112680094188086, 2136024671422363671272

Offset: 0

Author

Alois P. Heinz, Jun 07 2015

Keywords

• nonn

Comments

a(0) = 1 by convention.

a(n) >= n! = A000142(n).

Examples

			a(1) = 1: (1).
a(2) = 3: (12), (2)(1).
a(3) = 8: (123), (13)2, 2(13), (23)1, 3(12), (3)(2)(1).
		

Links

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

Crossrefs

Cf. A000142, A008304, A167999.

Programs

Maple

b:= proc(u, o, l, m, c) option remember;  `if`(u+o=0, `if`(l>m, 1,
      `if`(lm, 1, `if`(l b(n, 0$4):
seq(a(n), n=0..25);

Mathematica

b[u_, o_, l_, m_, c_] := b[u, o, l, m, c] = If[u + o == 0, If[l > m, 1,
     If[l < m, c, c + 1]], Sum[b[u - j, o + j - 1, 1, Max[l, m],
     If[l > m, 1, If[l < m, c, c + 1]]], {j, 1, u}] +
           Sum[b[u+j-1, o-j, l+1, m, c], {j, 1, o}]];
a[n_] :=  b[n, 0, 0, 0, 0];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 15 2022, after Alois P. Heinz *)