A336718 Total number of left-to-right maxima in all compositions of n into distinct parts.

0, 1, 1, 4, 4, 7, 18, 21, 32, 46, 107, 121, 193, 257, 379, 728, 900, 1299, 1806, 2529, 3360, 6182, 7387, 10807, 14385, 20217, 26207, 36450, 58194, 72887, 101130, 135379, 183178, 240796, 323307, 417625, 649959, 797623, 1096645, 1426108, 1931340, 2470541

Offset

0,4

Comments

Also total number of left-to-right minima in all compositions of n into distinct parts.

Links

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

Formula

a(n) = Sum_{k=1..floor((sqrt(8*n+1)-1)/2)} A000254(k) * A008289(n,k).

Example

a(6) = 18 = 3+2+2+2+1+1+2+1+2+1+1: (1)(2)(3), (1)(3)2, (2)1(3), (2)(3)1, (3)12, (3)21, (2)(4), (4)2, (1)(5), (5)1, (6).

Maple

g:= proc(n) option remember;
      `if`(n<2, n, (2*n-1)*g(n-1)-(n-1)^2*g(n-2))
    end:
b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,
      `if`(n=0, g(p), b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);

Mathematica

g[n_] := g[n] = If[n < 2, n, (2 n - 1) g[n - 1] - (n - 1)^2 g[n - 2]];
b[n_, i_, p_] := b[n, i, p] = If[i (i + 1)/2 < n, 0, If[n == 0, g[p], b[n, i - 1, p] + b[n - i, Min[n - i, i - 1], p + 1]]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 12 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000254, A003056, A008289, A032020, A336482, A336770, A336771.

Sequence in context: A115292 A202676 A330765 * A173324 A318243 A321661

Adjacent sequences: A336715 A336716 A336717 * A336719 A336720 A336721

Keyword

nonn

Author

Alois P. Heinz, Aug 01 2020

Status

approved