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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A018819 Binary partition function: number of partitions of n into powers of 2. 37
1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

First differences of A000123; also A000123 with terms repeated.

Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.

Euler transform of A036987 with offset 1.

a(n) = number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003

Normally the OEIS does not include sequences like this where every terms is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.

Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g. a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket, e.g. this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004

Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007

Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008

Appears to be row sums of A155077. [From Mats Granvik, Jan 19 2009]

Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as non-increasing lists).

Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. -  Gary W. Adamson, Nov 21 2009

Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). [Gary W. Adamson, Dec 05 2009]

REFERENCES

Bakoev V., Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41.

J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045. - From N. J. A. Sloane, Feb 03 2013

M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, http://www.math.ucla.edu/~pak/papers/CayleyComp4.pdf. - From N. J. A. Sloane, Dec 22 2012

O. J. Rodseth and J. A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.

D. Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.

LINKS

T. D. Noe, Table of n, a(n) for n = 0..1000

Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic

G. Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110. [From Giedrius Alkauskas (giedrius.alkauskas(AT)gmail.com), Mar 04 2010] [broken link]

Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 48, 581

M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.

N. J. A. Sloane and J. A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

FORMULA

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.

G.f.: 1 / Product_{j = 0..inf} (1-x^(2^j)).

a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002

a(n) = 1 if n = 0, Sum(j = 0..[n/2], a(j)) if n > 0. - David W. Wilson, Aug 16 2007

G.f. A(x) satisfies A(x^2) = (1-x)A(x). - Michael Somos, Aug 25 2003

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2w  - 2uv^2 + v^3. - Michael Somos, Apr 10 2005

G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006

G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). [Paul D. Hanna, Jan 23 2012]

Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. [Joerg Arndt, Dec 17 2012]

G.f.: prod(n>=0, (1+x^(2^n))^(n+1) ), see the fxtbook link. [Joerg Arndt, Feb 28 2014]

EXAMPLE

a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.

From Joerg Arndt, Dec 17 2012: (Start)

The a(10) = 14 binary partitions of 10 are (in lexicographic order)

[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]

[ 2]  [ 2 1 1 1 1 1 1 1 1 ]

[ 3]  [ 2 2 1 1 1 1 1 1 ]

[ 4]  [ 2 2 2 1 1 1 1 ]

[ 5]  [ 2 2 2 2 1 1 ]

[ 6]  [ 2 2 2 2 2 ]

[ 7]  [ 4 1 1 1 1 1 1 ]

[ 8]  [ 4 2 1 1 1 1 ]

[ 9]  [ 4 2 2 1 1 ]

[10]  [ 4 2 2 2 ]

[11]  [ 4 4 1 1 ]

[12]  [ 4 4 2 ]

[13]  [ 8 1 1 ]

[14]  [ 8 2 ]

The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.

The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)

[ 1]  [ 6 3 1 1 ]

[ 2]  [ 6 3 2 ]

[ 3]  [ 6 4 1 ]

[ 4]  [ 6 5 ]

[ 5]  [ 7 2 1 1 ]

[ 6]  [ 7 2 2 ]

[ 7]  [ 7 3 1 ]

[ 8]  [ 7 4 ]

[ 9]  [ 8 2 1 ]

[10]  [ 8 3 ]

[11]  [ 9 1 1 ]

[12]  [ 9 2 ]

[13]  [ 10 1 ]

[14]  [ 11 ]

The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.

(End)

For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

MAPLE

with(combinat); N:=8; a:=array(1..N); c:=array(1..N);

for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;

for s to np do r:=p[s]; r:=sort(r, `>`); nr:=nops(r); j:=1;

# while j<nr and r[j]>sum(r[k], k=j+1..nr) do j:=j+1; od; # gives A040039

while j<nr and r[j]>= sum(r[k], k=j+1..nr) do j:=j+1; od; # gives A018819

if j=nr then t:=t+1; fi od; a[n]:=t; od; # John McKay

MATHEMATICA

max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]

(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-Fran├žois Alcover, May 17 2011, updated Feb 17 2014 *)

PROG

(PARI) { n=15; v=vector(n); for (i=1, n, v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2, n, k=length(v[i-1]); for (j=1, k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*2)); c=vector(n); for (i=1, n, for (j=1, 2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */

(PARI) {a(n)=local(A, m); if(n<1, n==0, m=1; A=1+O(x); while(m<=n, m*=2; A=subst(A, x, x^2)/(1-x)); polcoeff(A, n))} /* Michael Somos, Apr 10 2005 */

(PARI) {a(n)=if(n<1, n==0, if(n%2, a(n-1), a(n/2)+a(n-1)))}

(Haskell)

a018819 n = a018819_list !! n

a018819_list = 1 : f (tail a008619_list) where

   f (x:xs) = (sum $ take x a018819_list) : f xs

-- Reinhard Zumkeller, Jan 28 2012

CROSSREFS

A000123(n) = a(2n) = a(2n+1). A000123 is the main entry for the binary partition function and gives many more properties and references.

Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).

Convolution inverse of A106400.

Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.

Sequence in context: A008643 A008644 A008645 * A211511 A211513 A127370

Adjacent sequences:  A018816 A018817 A018818 * A018820 A018821 A018822

KEYWORD

nonn,nice,easy,changed

AUTHOR

David W. Wilson, N. J. A. Sloane and J. H. Conway

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified September 1 22:05 EDT 2014. Contains 246317 sequences.