OFFSET
0,3
COMMENTS
Gives the number of multisets that occurring as the peak heights multiset of a Dyck (n+1)-path minus the number of multisets occurring as the peak heights multiset of a Dyck n-path. 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.
LINKS
D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
FORMULA
G.f.: 1/(1-2x) - Product_{k>0} 1/(1-x^k).
EXAMPLE
For n=2 the possibilities are UDUD, UUDD giving us multisets of {1,1} and {2} respectively. For n=1 there is only the one possibility UD giving us {1}. Thus a(1) = 2 - 1 = 1.
MAPLE
a:= n-> 2^n-combinat[numbpart](n):
seq(a(n), n=0..35); # Alois P. Heinz, Feb 14 2024
MATHEMATICA
Table[2^n - PartitionsP[n], {n, 0, 40}]
PROG
(PARI) a(n) = 2^n - numbpart(n); \\ Michel Marcus, Jul 05 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
David Nacin, Mar 01 2012
EXTENSIONS
Missing a(0)=0 inserted by Alois P. Heinz, Feb 14 2024
STATUS
approved