|
|
A208739
|
|
2^n minus the number of partitions of n.
|
|
2
|
|
|
0, 1, 2, 5, 11, 25, 53, 113, 234, 482, 982, 1992, 4019, 8091, 16249, 32592, 65305, 130775, 261759, 523798, 1047949, 2096360, 4193302, 8387353, 16775641, 33552474, 67106428, 134214718, 268431738, 536866347, 1073736220, 2147476806, 4294958947, 8589924449
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Gives the number of multisets that occurring as the peak heights multiset of a Dyck (n+1)-path minus the number of multisets occurring as the peak heights multiset of a Dyck n-path. 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.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1/(1-2x) - Product_{k>0} 1/(1-x^k).
|
|
EXAMPLE
|
For n=2 the possibilities are UDUD, UUDD giving us multisets of {1,1} and {2} respectively. For n=1 there is only the one possibility UD giving us {1}. Thus a(1) = 2 - 1 = 1.
|
|
MAPLE
|
a:= n-> 2^n-combinat[numbpart](n):
|
|
MATHEMATICA
|
Table[2^n - PartitionsP[n], {n, 0, 40}]
|
|
PROG
|
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|