# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a018819
Showing 1-1 of 1
%I A018819 #197 Jun 20 2024 17:22:06
%S A018819 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,
%T A018819 94,114,114,140,140,166,166,202,202,238,238,284,284,330,330,390,390,
%U A018819 450,450,524,524,598,598,692,692,786,786,900,900,1014,1014,1154,1154,1294,1294
%N A018819 Binary partition function: number of partitions of n into powers of 2.
%C A018819 First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
%C A018819 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.
%C A018819 Euler transform of A036987 with offset 1.
%C A018819 a(n) is the 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
%C A018819 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.
%C A018819 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
%C A018819 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
%C A018819 Differs from A008645 first at a(64). - _R. J. Mathar_, May 28 2008
%C A018819 Appears to be row sums of A155077. - _Mats Granvik_, Jan 19 2009
%C A018819 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 nonincreasing lists).
%C A018819 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
%C A018819 Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - _Gary W. Adamson_, Dec 05 2009
%C A018819 Let B = the n-th 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
%C A018819 From _Gary W. Adamson_, Sep 08 2016: (Start)
%C A018819 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:
%C A018819 1, 0, 0, 0, 0, ...
%C A018819 1, 0, 0, 0, 0, ...
%C A018819 1, 1, 0, 0, 0, ...
%C A018819 1, 1, 0, 0, 0, ...
%C A018819 1, 1, 1, 0, 0, ...
%C A018819 1, 1, 1, 0, 0, ...
%C A018819 1, 1, 1, 1, 0, ...
%C A018819 1, 1, 1, 1, 0, ...
%C A018819 1, 1, 1, 1, 1, ...
%C A018819 ... (End)
%C A018819 a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - _David V. Feldman_, Jan 29 2020
%C A018819 From _Gus Wiseman_, May 25 2024: (Start)
%C A018819 Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
%C A018819 {1} {2} {12} {3} {13} {23} {123} {4}
%C A018819 {11} {111} {22} {122} {113} {1113} {33}
%C A018819 {112} {1112} {222} {1222} {223}
%C A018819 {1111} {11111} {1122} {11122} {1123}
%C A018819 {11112} {111112} {2222}
%C A018819 {111111} {1111111} {11113}
%C A018819 {11222}
%C A018819 {111122}
%C A018819 {1111112}
%C A018819 {11111111}
%C A018819 (End)
%H A018819 T. D. Noe, Table of n, a(n) for n = 0..1000
%H A018819 Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic
%H A018819 Giedrius Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110.
%H A018819 Giedrius Alkauskas, Congruence Properties of the Function that Counts Compositions into Powers of 2 , J. Int. Seq. 13 (2010), 10.5.3.
%H A018819 Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.
%H A018819 Scott M. Bailey and Donald M. Larson, The A(1)-module structure of the homology of Brown-Gitler spectra, arXiv:2107.01316 [math.AT], 2021.
%H A018819 Valentin P. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.
%H A018819 Philippe Biane, Laver tables and combinatorics, arXiv:1810.00548 [math.CO], 2018. Mentions this sequence.
%H A018819 Peter J. Cameron, Firdous Ee Jannat, Rajat Kanti Nath, and Reza Sharafdini, A survey on conjugacy class graphs of groups, arXiv:2403.09423 [math.GR], 2024.
%H A018819 Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
%H A018819 Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 48, 581.
%H A018819 Maciej Gawron, Piotr Miska and Maciej Ulas, Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t, arXiv:1703.01955 [math.NT], 2017.
%H A018819 Michael D. Hirschhorn and James A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.
%H A018819 Jonathan Jordan and Richard 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
%H A018819 Yasuyuki Kachi and Pavlos Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
%H A018819 Matjaž Konvalinka and Igor Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91; see also DOI link. - From _N. J. A. Sloane_, Dec 22 2012
%H A018819 Apisit Pakapongpun and Thomas Ward, Functorial Orbit counting, J. Int. Seq., 12 (2009) 09.2.4, example 25.
%H A018819 Øystein J. Rodseth and James A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
%H A018819 David Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
%H A018819 N. J. A. Sloane and James A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
%H A018819 N. J. A. Sloane and James A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.
%F A018819 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.
%F A018819 G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
%F A018819 a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - _Vladeta Jovovic_, Aug 22 2002
%F A018819 a(2*n) = a(2*n + 1) = A000123(n). - _Michael Somos_, Aug 25 2003
%F A018819 a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - _David W. Wilson_, Aug 16 2007
%F A018819 G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - _Michael Somos_, Aug 25 2003
%F A018819 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
%F A018819 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
%F A018819 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
%F A018819 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
%F A018819 G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - _Joerg Arndt_, Feb 28 2014
%F A018819 G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - _Ilya Gutkovskiy_, May 07 2017
%e A018819 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 + ...
%e A018819 a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
%e A018819 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.
%e A018819 From _Joerg Arndt_, Dec 17 2012: (Start)
%e A018819 The a(10) = 14 binary partitions of 10 are (in lexicographic order)
%e A018819 [ 1] [ 1 1 1 1 1 1 1 1 1 1 ]
%e A018819 [ 2] [ 2 1 1 1 1 1 1 1 1 ]
%e A018819 [ 3] [ 2 2 1 1 1 1 1 1 ]
%e A018819 [ 4] [ 2 2 2 1 1 1 1 ]
%e A018819 [ 5] [ 2 2 2 2 1 1 ]
%e A018819 [ 6] [ 2 2 2 2 2 ]
%e A018819 [ 7] [ 4 1 1 1 1 1 1 ]
%e A018819 [ 8] [ 4 2 1 1 1 1 ]
%e A018819 [ 9] [ 4 2 2 1 1 ]
%e A018819 [10] [ 4 2 2 2 ]
%e A018819 [11] [ 4 4 1 1 ]
%e A018819 [12] [ 4 4 2 ]
%e A018819 [13] [ 8 1 1 ]
%e A018819 [14] [ 8 2 ]
%e A018819 The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
%e A018819 The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
%e A018819 [ 1] [ 6 3 1 1 ]
%e A018819 [ 2] [ 6 3 2 ]
%e A018819 [ 3] [ 6 4 1 ]
%e A018819 [ 4] [ 6 5 ]
%e A018819 [ 5] [ 7 2 1 1 ]
%e A018819 [ 6] [ 7 2 2 ]
%e A018819 [ 7] [ 7 3 1 ]
%e A018819 [ 8] [ 7 4 ]
%e A018819 [ 9] [ 8 2 1 ]
%e A018819 [10] [ 8 3 ]
%e A018819 [11] [ 9 1 1 ]
%e A018819 [12] [ 9 2 ]
%e A018819 [13] [ 10 1 ]
%e A018819 [14] [ 11 ]
%e A018819 The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
%e A018819 (End)
%e A018819 From _David V. Feldman_, Jan 29 2020: (Start)
%e A018819 The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
%e A018819 [ 1] [1 1 1 1 1 1 1 1 1 1]
%e A018819 [ 2] [2 2 2 2 2]
%e A018819 [ 3] [3 1 1 1 1 1 1 1]
%e A018819 [ 4] [3 3 1 1 1 1]
%e A018819 [ 5] [3 3 2 2]
%e A018819 [ 6] [3 3 3 1]
%e A018819 [ 7] [5 1 1 1 1 1]
%e A018819 [ 8] [5 5]
%e A018819 [ 9] [6 2 2]
%e A018819 [10] [6 4]
%e A018819 [11] [7 1 1 1]
%e A018819 [12] [7 3]
%e A018819 [13] [9 1]
%e A018819 [14] [10]
%e A018819 The a(11) = 14 non-borrowing 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.
%e A018819 (End)
%e A018819 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.
%p A018819 with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
%p A018819 for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
%p A018819 for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
%p A018819 # while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
%p A018819 while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
%p A018819 if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay
%t A018819 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}]
%t A018819 (* 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 *)
%t A018819 a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* _Michael Somos_, May 04 2022 *)
%t A018819 Table[Count[IntegerPartitions[n],_?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale_, Jun 20 2024 *)
%o A018819 (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_ */
%o A018819 (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 */
%o A018819 (PARI) {a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* _Michael Somos_, Aug 25 2003 */
%o A018819 (Haskell)
%o A018819 a018819 n = a018819_list !! n
%o A018819 a018819_list = 1 : f (tail a008619_list) where
%o A018819 f (x:xs) = (sum $ take x a018819_list) : f xs
%o A018819 -- _Reinhard Zumkeller_, Jan 28 2012
%o A018819 (Haskell)
%o A018819 import Data.List (intersperse)
%o A018819 a018819 = (a018819_list !!)
%o A018819 a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
%o A018819 -- _Johan Wiltink_, Nov 08 2018
%o A018819 (Python)
%o A018819 from functools import lru_cache
%o A018819 @lru_cache(maxsize=None)
%o A018819 def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # _Chai Wah Wu_, Jan 18 2022
%Y A018819 A000123 is the main entry for the binary partition function and gives many more properties and references.
%Y A018819 Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
%Y A018819 Convolution inverse of A106400.
%Y A018819 Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
%Y A018819 Multiplicity of n in A048675, for distinct prime indices A087207.
%Y A018819 Row lengths of A277905.
%Y A018819 A118462 lists binary ranks of strict integer partitions, row sums A372888.
%Y A018819 A372890 adds up binary ranks of integer partitions.
%Y A018819 Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
%Y A018819 Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.
%K A018819 nonn,nice,easy
%O A018819 0,3
%A A018819 _David W. Wilson_, _N. J. A. Sloane_ and _J. H. Conway_
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE