login
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
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
D. Callan and E. Deutsch, Problems and Solutions: 11624, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
FORMULA
a(n) = A208738(n+1) - A208738(n).
G.f.: 1/(1-2x) - Product_{k>0} 1/(1-x^k).
a(n) = A000079(n) - A000041(n). - Alois P. Heinz, Feb 14 2024
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):
seq(a(n), n=0..35); # Alois P. Heinz, Feb 14 2024
MATHEMATICA
Table[2^n - PartitionsP[n], {n, 0, 40}]
PROG
(PARI) a(n) = 2^n - numbpart(n); \\ Michel Marcus, Jul 05 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
David Nacin, Mar 01 2012
EXTENSIONS
Missing a(0)=0 inserted by Alois P. Heinz, Feb 14 2024
STATUS
approved