0,3

First differences of A000123; also A000123 doubled up.

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. - njas, 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 (perry(AT)globalnet.co.uk), 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 (vladeta(AT)Eunet.yu), Aug 06 2007

Differs from A008645 first at a(64). - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), May 28 2008

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.

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

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

M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions

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

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 (vladeta(AT)Eunet.yu), Aug 22 2002

a(n) = 1 if n = 0, Sum(j = 0..[n/2], a(j)) if n > 0. - David W. Wilson (davidwwilson(AT)comcast.net), 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

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

(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)))}

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.

Sequence in context: A008643 A008644 A008645 this_sequence A127370 A106247 A094909

Adjacent sequences: A018816 A018817 A018818 this_sequence A018820 A018821 A018822

nonn,nice,easy

David W. Wilson (davidwwilson(AT)comcast.net), njas and J. H. Conway (conway(AT)math.princeton.edu)