A002843 Number of partitions of n into parts 1/2, 3/4, 7/8, 15/16, etc.
1, 1, 2, 4, 7, 13, 24, 43, 78, 141, 253, 456, 820, 1472, 2645, 4749, 8523, 15299, 27456, 49267, 88407, 158630, 284622, 510683, 916271, 1643963, 2949570, 5292027, 9494758, 17035112, 30563634, 54835835, 98383803, 176515310, 316694823, 568197628, 1019430782
Offset: 0
Examples
A straightforward partition problem: 1 = 1/2 + 1/2 and there is no other partition of 1, so a(1)=1. a(3)=4 since 3 = 6(1/2) = 4(3/4) = 2(3/4) + 3(1/2) = 2(7/8) + 3/4 + 1/2. 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. From _Joerg Arndt_, Dec 28 2012: (Start) There are a(6)=24 compositions of 6 where part(k) <= 2 * part(k-1): [ 1] [ 1 1 1 1 1 1 ] [ 2] [ 1 1 1 1 2 ] [ 3] [ 1 1 1 2 1 ] [ 4] [ 1 1 2 1 1 ] [ 5] [ 1 1 2 2 ] [ 6] [ 1 2 1 1 1 ] [ 7] [ 1 2 1 2 ] [ 8] [ 1 2 2 1 ] [ 9] [ 1 2 3 ] [10] [ 2 1 1 1 1 ] [11] [ 2 1 1 2 ] [12] [ 2 1 2 1 ] [13] [ 2 2 1 1 ] [14] [ 2 2 2 ] [15] [ 2 3 1 ] [16] [ 2 4 ] [17] [ 3 1 1 1 ] [18] [ 3 1 2 ] [19] [ 3 2 1 ] [20] [ 3 3 ] [21] [ 4 1 1 ] [22] [ 4 2 ] [23] [ 5 1 ] [24] [ 6 ] (End)
References
- 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.
- N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 201 terms from Vincenzo Librandi)
- David Benson, Pavel Etingof, On cohomology in symmetric tensor categories in prime characteristic, arXiv:2008.13149 [math.RT], 2020.
- R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
- H. Minc, 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.
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Programs
-
Maple
b:= proc(n, i) option remember; `if`(n=0, 1, add(b(n-j, min(n-j, 2*j)), j=1..i)) end: a:= n-> b(n$2): seq(a(n), n=0..40); # Alois P. Heinz, Jun 24 2017 -
Mathematica
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 *)
Formula
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.
Extensions
More terms from John W. Layman, Nov 24 2001
Examples and offset corrected by Larry Reeves (larryr(AT)acm.org), Jan 06 2005
Further terms from Vladeta Jovovic, Mar 13 2006
Comments