|
%I #23 Jul 22 2020 11:42:35
%S 0,0,0,1,4,13,34,83,189,415,885,1853,3824,7819,15876,32084,64621,
%T 129860,260547,522201,1045862,2093646,4189796,8382845,16769878,
%U 33545136,67097132,134202986,268416996,536847887,1073713195,2147448177,4294923476,8589880629
%N Number of multisets that occurring as the peak heights multiset of a Dyck n-path that are the also the peak heights multiset of a smaller Dyck path.
%C We use the definition given by Callan and Deutsch (see reference). A Dyck n-path is a lattice path of n upsteps U (changing by (1,1)) and n downsteps D (changing by (1,-1)) that starts at the origin and never goes below the x-axis. A peak is an occurrence of U D and the peak height is the y-coordinate of the vertex between its U and D.
%C Also the number of nonempty multisets S of positive integers satisfying max(S) + |S| <= n <= sum(S).
%H Vincenzo Librandi, <a href="/A208740/b208740.txt">Table of n, a(n) for n = 1..1000</a>
%H D. Callan and E. Deutsch, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.119.02.161">Problems and Solutions: 11624</a>, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
%F a(n) = 2^(n-1) - A000070(n-1).
%F a(n) = A208738(n) - 2^(n-1).
%F G.f.: x/(1-2*x)-(x/(1-x))*product(m>=1, 1/(1-x^m)).
%e For a Dyck 4-path there is only one peak heights multiset occurring also for a Dyck 3-path. This is {2,2} and occurs for both UUDDUUDD when n=4 and UUDUDD when n=3.
%t Table[2^(n - 1) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]
%o (PARI) a(n) = 2^(n-1) - sum(k=0, n-1, numbpart(k)); \\ _Michel Marcus_, Jul 07 2018
%Y Cf. A000070, A208738, A208739.
%K nonn
%O 1,5
%A _David Nacin_, Mar 01 2012
|
