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

Author

Alois P. Heinz, Aug 01 2020

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Programs

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

Formula

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