A208739 2^n minus the number of partitions of n.

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

Table of n, a(n) for n=0..33.

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

Cf. A000041, A000079, A208738, A208740.

Sequence in context: A084978 A118036 A291552 * A291737 A177795 A092685

Adjacent sequences: A208736 A208737 A208738 * A208740 A208741 A208742

Keyword

nonn

Author

David Nacin, Mar 01 2012

Extensions

Missing a(0)=0 inserted by Alois P. Heinz, Feb 14 2024

Status

approved