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

Author

David Nacin, Mar 01 2012

Keywords

• nonn

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).

Examples

			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.
		

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.

Crossrefs

Cf. A000041, A000070, A000108, A058884.

Partial differences give A208739.

Programs

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}]

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))

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).

Extensions

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