cp's OEIS Frontend

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

%I A336718 #22 Jul 12 2021 04:16:15
%S A336718 0,1,1,4,4,7,18,21,32,46,107,121,193,257,379,728,900,1299,1806,2529,
%T A336718 3360,6182,7387,10807,14385,20217,26207,36450,58194,72887,101130,
%U A336718 135379,183178,240796,323307,417625,649959,797623,1096645,1426108,1931340,2470541
%N A336718 Total number of left-to-right maxima in all compositions of n into distinct parts.
%C A336718 Also total number of left-to-right minima in all compositions of n into distinct parts.
%H A336718 Alois P. Heinz, <a href="/A336718/b336718.txt">Table of n, a(n) for n = 0..5000</a>
%F A336718 a(n) = Sum_{k=1..floor((sqrt(8*n+1)-1)/2)} A000254(k) * A008289(n,k).
%e A336718 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 A336718 g:= proc(n) option remember;
%p A336718       `if`(n<2, n, (2*n-1)*g(n-1)-(n-1)^2*g(n-2))
%p A336718     end:
%p A336718 b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,
%p A336718       `if`(n=0, g(p), b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))
%p A336718     end:
%p A336718 a:= n-> b(n$2, 0):
%p A336718 seq(a(n), n=0..50);
%t A336718 g[n_] := g[n] = If[n < 2, n, (2 n - 1) g[n - 1] - (n - 1)^2 g[n - 2]];
%t A336718 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 A336718 a[n_] := b[n, n, 0];
%t A336718 Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Jul 12 2021, after _Alois P. Heinz_ *)
%Y A336718 Cf. A000254, A003056, A008289, A032020, A336482, A336770, A336771.
%K A336718 nonn
%O A336718 0,4
%A A336718 _Alois P. Heinz_, Aug 01 2020