OFFSET
1,5
COMMENTS
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.
Also the number of nonempty multisets S of positive integers satisfying max(S) + |S| <= n <= sum(S).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..1000
D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
FORMULA
EXAMPLE
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.
MATHEMATICA
Table[2^(n - 1) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]
PROG
(PARI) a(n) = 2^(n-1) - sum(k=0, n-1, numbpart(k)); \\ Michel Marcus, Jul 07 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
David Nacin, Mar 01 2012
STATUS
approved