A208740 Number of multisets that occurring as the peak heights multiset of a Dyck n-path that are the also the peak heights multiset of a smaller Dyck path.

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

Offset: 1

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

Examples

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

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.

Crossrefs

Cf. A000070, A208738, A208739.

Programs

Mathematica

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

PARI

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

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