

A018819


Binary partition function: number of partitions of n into powers of 2.


126



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. See the relevant proof that follows the first formula below.
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) is the number of "nonsquashing" 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 term 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 AdamsWatters link.  Vladeta Jovovic, Aug 06 2007
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 "nonsquashing" partitions as nonincreasing lists).
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...).  Gary W. Adamson, Dec 05 2009
Let B = the nth convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...).  Gary W. Adamson, Aug 15 2016
The limit of the matrix power M^k as n>inf results in a single column vector equal to the sequence, where M is the following production matrix:
1, 0, 0, 0, 0, ...
1, 0, 0, 0, 0, ...
1, 1, 0, 0, 0, ...
1, 1, 0, 0, 0, ...
1, 1, 1, 0, 0, ...
1, 1, 1, 0, 0, ...
1, 1, 1, 1, 0, ...
1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, ...
... (End)
a(n) is the number of "nonborrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require placevalue borrowing.  David V. Feldman, Jan 29 2020


LINKS

M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 8691; see also DOI link.  From N. J. A. Sloane, Dec 22 2012


FORMULA

a(2m+1) = a(2m), a(2m) = a(2m1) + 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} (1x^(2^j)).
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0.  David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1x) * 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^2*w  2*u*v^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
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1A)^k  (A)^k) + (A)^k, see fxtbook link.  Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link.  Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1  x^(2^j)).  Ilya Gutkovskiy, May 07 2017


EXAMPLE

G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
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.
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 nonsquashing 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 nonsquashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
The a(10) = 14 nonborrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 nonborrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(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[n1]; a[n_?EvenQ] := a[n] = a[n1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* JeanFrançois Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n1] + If[EvenQ@n, a[Quotient[n, 2]], 0]]; (* Michael Somos, May 04 2022 *)


PROG

(PARI) { n=15; v=vector(n); for (i=1, n, v[i]=vector(2^(i1))); v[1][1]=1; for (i=2, n, k=length(v[i1]); for (j=1, k, v[i][j]=v[i1][j]+1; v[i][j+k]=v[i1][j]*2)); c=vector(n); for (i=1, n, for (j=1, 2^(i1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */
(PARI) {a(n) = my(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, Aug 25 2003 */
(PARI) {a(n) = if( n<1, n==0, if( n%2, a(n1), a(n/2)+a(n1)))}; /* Michael Somos, Aug 25 2003 */
(Haskell)
a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
f (x:xs) = (sum $ take x a018819_list) : f xs
(Haskell)
import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)


CROSSREFS

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled nonsquashing partitions).
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.


KEYWORD

nonn,nice,easy


AUTHOR



STATUS

approved



