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

%I #22 Jul 12 2021 04:16:15

%S 0,1,1,4,4,7,18,21,32,46,107,121,193,257,379,728,900,1299,1806,2529,

%T 3360,6182,7387,10807,14385,20217,26207,36450,58194,72887,101130,

%U 135379,183178,240796,323307,417625,649959,797623,1096645,1426108,1931340,2470541

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

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

%H Alois P. Heinz, <a href="/A336718/b336718.txt">Table of n, a(n) for n = 0..5000</a>

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

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

%p g:= proc(n) option remember;

%p `if`(n<2, n, (2*n-1)*g(n-1)-(n-1)^2*g(n-2))

%p end:

%p b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, g(p), b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))

%p end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..50);

%t g[n_] := g[n] = If[n < 2, n, (2 n - 1) g[n - 1] - (n - 1)^2 g[n - 2]];

%t 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]]];

%t a[n_] := b[n, n, 0];

%t Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Jul 12 2021, after _Alois P. Heinz_ *)

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

%K nonn

%O 0,4

%A _Alois P. Heinz_, Aug 01 2020