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