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

Links

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

Example

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

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

Crossrefs

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

Sequence in context: A090764 A182557 A027934 * A134389 A286945 A371797

Adjacent sequences: A336479 A336480 A336481 * A336483 A336484 A336485

Keyword

nonn

Author

Alois P. Heinz, Jul 22 2020

Status

approved