cp's OEIS Frontend

A002843 Number of partitions of n into parts 1/2, 3/4, 7/8, 15/16, etc.

%I A002843 M1072 N0405 #61 Jan 15 2024 12:02:23
%S A002843 1,1,2,4,7,13,24,43,78,141,253,456,820,1472,2645,4749,8523,15299,
%T A002843 27456,49267,88407,158630,284622,510683,916271,1643963,2949570,
%U A002843 5292027,9494758,17035112,30563634,54835835,98383803,176515310,316694823,568197628,1019430782
%N A002843 Number of partitions of n into parts 1/2, 3/4, 7/8, 15/16, etc.
%C A002843 Row sums of A049286 and A047913. [_Vladeta Jovovic_, Dec 02 2009]
%C A002843 Also number of compositions (a_1,a_2,...) of n with each a_i <= 2*a_(i-1). [_Vladeta Jovovic_, Dec 02 2009]
%D A002843 Minc, H.; A problem in partitions: Enumeration of elements of a given degree in the free commutative entropic cyclic groupoid. Proc. Edinburgh Math. Soc. (2) 11 1958/1959 223-224.
%D A002843 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002843 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002843 Alois P. Heinz, <a href="/A002843/b002843.txt">Table of n, a(n) for n = 0..2000</a> (first 201 terms from Vincenzo Librandi)
%H A002843 David Benson, Pavel Etingof, <a href="https://arxiv.org/abs/2008.13149">On cohomology in symmetric tensor categories in prime characteristic</a>, arXiv:2008.13149 [math.RT], 2020.
%H A002843 R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: <a href="/A002572/a002572.jpg">front</a>, <a href="/A002572/a002572_1.jpg">back</a> [Annotated scanned copy, with permission]
%H A002843 H. Minc, <a href="http://dx.doi.org/10.1017/S0013091500021945">A problem in partitions: Enumeration of elements of a given degree in the free commutative entropic cyclic groupoid</a>, Proc. Edinburgh Math. Soc. (2) 11 1958/1959 223-224.
%H A002843 Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
%H A002843 Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992
%F A002843 The g.f. (z**2+z+1)*(z-1)**2/(1-2*z-z**3+3*z**4) conjectured by _Simon Plouffe_ in his 1992 dissertation is wrong.
%e A002843 A straightforward partition problem: 1 = 1/2 + 1/2 and there is no other partition of 1, so a(1)=1.
%e A002843 a(3)=4 since 3 = 6(1/2) = 4(3/4) = 2(3/4) + 3(1/2) = 2(7/8) + 3/4 + 1/2.
%e A002843 a(4)=7 since 4 = 8(1/2) = 5(1/2) + 2(3/4) = 2(1/2) + 4(3/4) = 3(1/2) + 3/4 + 2(7/8) = 3(3/4) + 2(7/8) = 1/2 + 4(7/8) = 2(15/16) + 7/8 + 3/4 + 1/2.
%e A002843 From _Joerg Arndt_, Dec 28 2012: (Start)
%e A002843 There are a(6)=24 compositions of 6 where part(k) <= 2 * part(k-1):
%e A002843 [ 1]  [ 1 1 1 1 1 1 ]
%e A002843 [ 2]  [ 1 1 1 1 2 ]
%e A002843 [ 3]  [ 1 1 1 2 1 ]
%e A002843 [ 4]  [ 1 1 2 1 1 ]
%e A002843 [ 5]  [ 1 1 2 2 ]
%e A002843 [ 6]  [ 1 2 1 1 1 ]
%e A002843 [ 7]  [ 1 2 1 2 ]
%e A002843 [ 8]  [ 1 2 2 1 ]
%e A002843 [ 9]  [ 1 2 3 ]
%e A002843 [10]  [ 2 1 1 1 1 ]
%e A002843 [11]  [ 2 1 1 2 ]
%e A002843 [12]  [ 2 1 2 1 ]
%e A002843 [13]  [ 2 2 1 1 ]
%e A002843 [14]  [ 2 2 2 ]
%e A002843 [15]  [ 2 3 1 ]
%e A002843 [16]  [ 2 4 ]
%e A002843 [17]  [ 3 1 1 1 ]
%e A002843 [18]  [ 3 1 2 ]
%e A002843 [19]  [ 3 2 1 ]
%e A002843 [20]  [ 3 3 ]
%e A002843 [21]  [ 4 1 1 ]
%e A002843 [22]  [ 4 2 ]
%e A002843 [23]  [ 5 1 ]
%e A002843 [24]  [ 6 ]
%e A002843 (End)
%p A002843 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A002843       add(b(n-j, min(n-j, 2*j)), j=1..i))
%p A002843     end:
%p A002843 a:= n-> b(n$2):
%p A002843 seq(a(n), n=0..40);  # _Alois P. Heinz_, Jun 24 2017
%t A002843 v[c_, d_] := v[c, d] = If[d < 0 || c < 0, 0, If[d == c, 1, Sum[v[i, d - c], {i, 1, 2*c}]]]; Join[{1}, Plus @@@ Table[v[d, c], {c, 1, 34}, {d, 1, c}]] (* _Jean-François Alcover_, Dec 10 2012, after _Vladeta Jovovic_ *)
%Y A002843 Cf. A047913, A049286.
%K A002843 nonn,nice
%O A002843 0,3
%A A002843 _N. J. A. Sloane_
%E A002843 More terms from _John W. Layman_, Nov 24 2001
%E A002843 Examples and offset corrected by Larry Reeves (larryr(AT)acm.org), Jan 06 2005
%E A002843 Further terms from _Vladeta Jovovic_, Mar 13 2006