OFFSET
0,3
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| - 1 <= n <= sum(S).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
David Callan and Emeric Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
Manosij Ghosh Dastidar and Michael Wallner, Bijections and congruences involving lattice paths and integer compositions, arXiv:2402.17849 [math.CO], 2024. See p. 14.
FORMULA
EXAMPLE
For n=2 the possibilities are UDUD, UUDD giving us multisets of {1,1} and {2} respectively. There are two distinct multisets so a(2) = 2.
MAPLE
a:= proc(n) a(n):= `if`(n=0, 1, a(n-1)+2^(n-1)-combinat[numbpart](n-1)) end:
seq(a(n), n=0..33); # Alois P. Heinz, Feb 14 2024
MATHEMATICA
Table[2^(n) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]
PROG
(Python)
#Returns all possible peak heights multisets
def peakheightsmultisets(n):
#Making all possible paths
allpaths=list()
combinst=itertools.combinations(range(2*n), n)
for tup in combinst:
a=[]
for i in range(2*n):
if i in tup:
a.append(1)
else:
a.append(-1)
allpaths.append(tuple(a))
#Now we take Dyck paths and form multisets as we go
output=set()
for x in allpaths:
include=True
peaklist=[]
total=0
for unit in x:
if unit==-1 and lastunit==1:
peaklist.append(total)
total+=unit
if total < 0:
include=False
break
lastunit=unit
if include:
output.add(tuple(sorted(peaklist)))
return output
(Python)
#Using peakheightsmultisets(n)
def a(n):
return len(peakheightsmultisets(n))
CROSSREFS
KEYWORD
nonn
AUTHOR
David Nacin, Mar 01 2012
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Feb 14 2024
STATUS
approved