login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A208740 Number of multisets that occuring as the peak heights multiset of a Dyck n-path that are the also the peak heights multiset of a smaller Dyck path. 2
0, 0, 0, 1, 4, 13, 34, 83, 189, 415, 885, 1853, 3824, 7819, 15876, 32084, 64621, 129860, 260547, 522201, 1045862, 2093646, 4189796, 8382845, 16769878, 33545136, 67097132, 134202986, 268416996, 536847887, 1073713195, 2147448177, 4294923476, 8589880629 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

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| <= n <= sum(S).

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.

FORMULA

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

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

G.f.: x/(1-2*x)-(x/(1-x))*product(m>=1, 1/(1-x^m)).

EXAMPLE

For a Dyck 4-path there is only one peak heights multiset occuring also for a Dyck 3-path. This is {2,2} and occurs for both UUDDUUDD when n=4 and UUDUDD when n=3.

MATHEMATICA

Table[2^(n - 1) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]

PROG

(PARI) a(n) = 2^(n-1) - sum(k=0, n-1, numbpart(k)); \\ Michel Marcus, Jul 07 2018

CROSSREFS

Cf. A000070, A208738, A208739.

Sequence in context: A262200 A213578 A212149 * A127981 A296303 A089453

Adjacent sequences:  A208737 A208738 A208739 * A208741 A208742 A208743

KEYWORD

nonn

AUTHOR

David Nacin, Mar 01 2012

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 22:10 EDT 2019. Contains 328373 sequences. (Running on oeis4.)