login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002843 Number of partitions of n into parts 1/2, 3/4, 7/8, 15/16, etc.
(Formerly M1072 N0405)
3
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

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.

Also number of compositions (a_1,a_2,...) of n with each a_i <= 2*a_(i-1). [Vladeta Jovovic, Dec 02 2009]

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)

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.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

FORMULA

Row sums of A049286 and A047913. [Vladeta Jovovic, Dec 02 2009]

EXAMPLE

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)

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 *)

CROSSREFS

Cf. A047913.

Sequence in context: A006745 A049284 A049285 * A128742 A318748 A107281

Adjacent sequences:  A002840 A002841 A002842 * A002844 A002845 A002846

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 08:26 EST 2019. Contains 320159 sequences. (Running on oeis4.)