|
|
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.
|
|
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
|
|
|
FORMULA
|
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 occurring 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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|