A336482 Total number of left-to-right maxima in all compositions of n.

0, 1, 2, 5, 11, 24, 51, 108, 226, 471, 976, 2015, 4146, 8508, 17418, 35590, 72597, 147868, 300797, 611202, 1240690, 2516268, 5099242, 10326282, 20897848, 42267257, 85442478, 172635651, 348651294, 703836046, 1420315254, 2865122304, 5777735296, 11647641296

Offset: 0

Author

Alois P. Heinz, Jul 22 2020

Keywords

• nonn

Examples

			a(4) = 11: (1)111, (1)1(2), (1)(2)1, (2)11, (2)2, (1)(3), (3)1, (4).
		

Links

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

Crossrefs

Cf. A000254 (the same for permutations of [n]), A225095, A336484, A336511, A336718, A382312.

Programs

Maple

b:= proc(n, m, c) option remember; `if`(n=0, c, add(
      b(n-j, max(m, j), c+`if`(j>m, 1, 0)), j=1..n))
    end:
a:= n-> b(n, -1, 0):
seq(a(n), n=0..50);

Mathematica

b[n_, m_, c_] := b[n, m, c] = If[n == 0, c, Sum[
     b[n - j, Max[m, j], c + If[j > m, 1, 0]], {j, 1, n}]];
a[n_] := b[n, -1, 0];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 04 2022, after Alois P. Heinz *)

PARI

T_xy(max_row) = {my(N=max_row+1, x='x+O('x^N), h= prod(i=1,N, 1 + y*x^i *(1-x)/(1-2*x+x^(i+1)))); h}
P_xy(N) = Pol(T_xy(N), {x})
B_x(N) = {my(cx = deriv(P_xy(N), y), y=1); Vecrev(eval(cx))}
B_x(30) \\ John Tyler Rascoe, Mar 22 2025

Formula

a(n) = Sum_{k>0} A382312(n,k)*k. - John Tyler Rascoe, Mar 22 2025