A208738 Number of multisets occurring as the peak heights multiset of a Dyck n-path.

1, 1, 2, 4, 9, 20, 45, 98, 211, 445, 927, 1909, 3901, 7920, 16011, 32260, 64852, 130157, 260932, 522691, 1046489, 2094438, 4190798, 8384100, 16771453, 33547094, 67099568, 134205996, 268420714, 536852452, 1073718799, 2147455019, 4294931825, 8589890772

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

a(n) = 2^n - A000070(n-1).

a(n) = 2*a(n-1) + A058884(n+1).

G.f.: 1/(1-2*x) - (x/(1-x)) * Product_{m>=1} 1/(1-x^m).

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

Cf. A000041, A000070, A000108, A058884.

Partial differences give A208739.

Sequence in context: A199296 A219229 A091620 * A144686 A108469 A085584

Adjacent sequences: A208735 A208736 A208737 * A208739 A208740 A208741

Keyword

nonn

Author

David Nacin, Mar 01 2012

Extensions

a(0)=1 prepended by Alois P. Heinz, Feb 14 2024

Status

approved