cp's OEIS Frontend

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

%I A208739 #21 Feb 14 2024 14:48:16
%S A208739 0,1,2,5,11,25,53,113,234,482,982,1992,4019,8091,16249,32592,65305,
%T A208739 130775,261759,523798,1047949,2096360,4193302,8387353,16775641,
%U A208739 33552474,67106428,134214718,268431738,536866347,1073736220,2147476806,4294958947,8589924449
%N A208739 2^n minus the number of partitions of n.
%C A208739 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.
%H A208739 D. Callan and E. Deutsch, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.119.02.161">Problems and Solutions: 11624</a>, The Amer. Math. Monthly 119 (2012), no. 2, 161-162.
%F A208739 a(n) = A208738(n+1) - A208738(n).
%F A208739 G.f.: 1/(1-2x) - Product_{k>0} 1/(1-x^k).
%F A208739 a(n) = A000079(n) - A000041(n). - _Alois P. Heinz_, Feb 14 2024
%e A208739 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.
%p A208739 a:= n-> 2^n-combinat[numbpart](n):
%p A208739 seq(a(n), n=0..35);  # _Alois P. Heinz_, Feb 14 2024
%t A208739 Table[2^n - PartitionsP[n], {n, 0, 40}]
%o A208739 (PARI) a(n) = 2^n - numbpart(n); \\ _Michel Marcus_, Jul 05 2018
%Y A208739 Cf. A000041, A000079, A208738, A208740.
%K A208739 nonn
%O A208739 0,3
%A A208739 _David Nacin_, Mar 01 2012
%E A208739 Missing a(0)=0 inserted by _Alois P. Heinz_, Feb 14 2024