login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000123 Number of binary partitions: number of partitions of 2n into powers of 2.
(Formerly M1011 N0378)
108

%I M1011 N0378 #260 Feb 21 2024 10:33:35

%S 1,2,4,6,10,14,20,26,36,46,60,74,94,114,140,166,202,238,284,330,390,

%T 450,524,598,692,786,900,1014,1154,1294,1460,1626,1828,2030,2268,2506,

%U 2790,3074,3404,3734,4124,4514,4964,5414,5938,6462,7060,7658,8350,9042,9828

%N Number of binary partitions: number of partitions of 2n into powers of 2.

%C Also, a(n) = number of "non-squashing" partitions of 2n (or 2n+1), that is, partitions 2n = 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 [Hirschhorn and Sellers].

%C Row sums of A101566. - _Paul Barry_, Jan 03 2005

%C Equals infinite convolution product of [1,2,2,2,2,2,2,2,2] aerated A000079 - 1 times, i.e., [1,2,2,2,2,2,2,2,2] * [1,0,2,0,2,0,2,0,2] * [1,0,0,0,2,0,0,0,2]. - _Mats Granvik_ and _Gary W. Adamson_, Aug 04 2009

%C Which can be further decomposed to the infinite convolution product of finally supported sequences, namely [1,1] aerated A000079 - 1 times with multiplicity A000027 + 1 times, i.e., [1,1] * [1,1] * [1,0,1] * [1,0,1] * [1,0,1] * ... (next terms are [1,0,0,0,1] 4 times, etc.). - _Eitan Y. Levine_, Jun 18 2023

%C Given A018819 = A000123 with repeats, polcoeff (1, 1, 2, 2, 4, 4, ...) * (1, 1, 1, ...) = (1, 2, 4, 6, 10, ...) = (1, 0, 2, 0, 4, 0, 6, ...) * (1, 2, 2, 2, ...). - _Gary W. Adamson_, Dec 16 2009

%C Let M = an infinite lower triangular matrix with (1, 2, 2, 2, ...) in every column shifted down twice. A000123 = lim_{n->infinity} M^n, the left-shifted vector considered as a sequence. Replacing (1, 2, 2, 2, ...) with (1, 3, 3, 3, ...) and following the same procedure, we obtain A171370: (1, 3, 6, 12, 18, 30, 42, 66, 84, 120, ...). - _Gary W. Adamson_, Dec 06 2009

%C First differences of the sequence are (1, 2, 2, 4, 4, 6, 6, 10, ...), A018819, i.e., the sequence itself with each term duplicated except for the first one (unless a 0 is prefixed before taking the first differences), as shown by the formula a(n) - a(n-1) = a(floor(n/2)), valid for all n including n = 0 if we let a(-1) = 0. - _M. F. Hasler_, Feb 19 2019

%C Sum over k <= n of number of partitions of k into powers of 2, A018819. - _Peter Munn_, Feb 21 2020

%D G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.

%D R. F. Churchhouse, Binary partitions, pp. 397-400 of A. O. L. Atkin and B. J. Birch, editors, Computers in Number Theory. Academic Press, NY, 1971.

%D N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.

%D H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.

%D H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A000123/b000123.txt">Table of n, a(n) for n = 0..65536</a> (first 10001 terms from T. D. Noe)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 728

%H C. Banderier, H.-K. Hwang, V. Ravelomanana and V. Zacharovas, <a href="http://140.109.74.92/hk/wp-content/files/2012/07/mis-n-to-the-logn.pdf">Analysis of an exhaustive search algorithm in random graphs and the n^{c logn}-asymptotics</a>, 2012. - From _N. J. A. Sloane_, Dec 23 2012

%H Sara Billey, Matjaž Konvalinka and Frederick A. Matsen IV, <a href="https://hal.archives-ouvertes.fr/hal-02173394">On trees, tanglegrams, and tangled chains</a>, hal-02173394 [math.CO], 2020.

%H Henry Bottomley, <a href="/A000123/a000123.gif">Illustration of initial terms</a>

%H N. G. de Bruijn, <a href="http://www.dwc.knaw.nl/DL/publications/PU00018536.pdf">On Mahler's partition problem</a>, 1948.

%H R. F. Churchhouse, <a href="http://dx.doi.org/10.1017/S0305004100045072">Congruence properties of the binary partition function</a>, Proc. Cambridge Philos. Soc. 66 1969 371-376.

%H Philippe Deléham, <a href="/A033485/a033485.pdf">Letter to N. J. A. Sloane, Apr 20 1998</a>

%H P. Dumas and P. Flajolet, <a href="http://jtnb.cedram.org/item?id=JTNB_1996__8_1_1_0">Asymptotique des recurrences mahleriennes: le cas cyclotomique</a>, Journal de Théorie des Nombres de Bordeaux 8 (1996), pp. 1-30.

%H Amanda Folsom et al, <a href="http://dx.doi.org/10.1016/j.disc.2015.12.019">On a general class of non-squashing partitions</a>, Discrete Mathematics 339.5 (2016): 1482-1506.

%H C.-E. Froberg, <a href="http://dx.doi.org/10.1007/BF01933448">Accurate estimation of the number of binary partitions</a>, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.

%H C.-E. Froberg, <a href="/A000123/a000123.pdf">Accurate estimation of the number of binary partitions</a> [Annotated scanned copy]

%H Maciej Gawron, Piotr Miska and Maciej Ulas, <a href="https://arxiv.org/abs/1703.01955">Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t</a>, arXiv:1703.01955 [math.NT], 2017.

%H H. Gupta, <a href="http://dx.doi.org/10.1017/S0305004100049665">Proof of the Churchhouse conjecture concerning binary partitions</a>, Proc. Camb. Phil. Soc. 70 (1971), 53-56.

%H R. K. Guy, <a href="/A000123/a000123_1.pdf">Letters to N. J. A. Sloane and J. W. Moon, 1988</a>

%H M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, <a href="https://ajc.maths.uq.edu.au/pdf/30/ajc_v30_p193.pdf">Australasian J. Combin.</a>, 30 (2004), 193-196.

%H M. D. Hirschhorn and J. A. Sellers, <a href="http://www.math.psu.edu/sellersj/mike-m-ary.pdf">A different view of m-ary partitions</a>

%H Youkow Homma, Jun Hwan Ryu and Benjamin Tong, <a href="http://sumry.yale.edu/sites/default/files/files/Sequence_nonsquashing_partitions.pdf">Sequence non-squashing partitions</a>, Slides from a talk, Jul 24 2014.

%H K. Ji and H. S. Wilf, <a href="http://www.jstor.org/stable/27642506">Extreme palindromes</a>, Amer. Math. Monthly, 115, no. 5 (2008), 447-451.

%H Y. Kachi and P. Tzermias, <a href="http://mi.mathnet.ru/adm508">On the m-ary partition numbers</a>, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.

%H Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.

%H D. E. Knuth, <a href="http://www.fq.math.ca/Scanned/4-2/knuth.pdf">An almost linear recurrence</a>, Fib. Quart., 4 (1966), 117-128.

%H M. Konvalinka and I. Pak, <a href="http://www.math.ucla.edu/~pak/papers/CayleyComp7.pdf">Cayley compositions, partitions, polytopes, and geometric bijections</a> - _N. J. A. Sloane_, Dec 22 2012

%H M. Konvalinka and I. Pak, <a href="https://doi.org/10.1016/j.jcta.2013.11.008">Cayley compositions, partitions, polytopes, and geometric bijections</a>, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91.

%H Vaclav Kotesovec, <a href="/A000123/a000123_2.pdf">Graph - the asymptotic ratio (10^8 terms)</a>

%H M. Latapy, <a href="https://doi.org/10.46298/dmtcs.2279">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.

%H M. Latapy, <a href="/A005706/a005706.pdf">Partitions of an integer into powers</a>, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]

%H K. Mahler, <a href="https://doi.org/10.1112/jlms/s1-15.2.115">On a special functional equation</a>, Journ. London Math. Soc. 15 (1940), 115-123.

%H E. O'Shea, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.016">M-partitions: optimal partitions of weight for one scale pan</a>, Discrete Math. 289 (2004), 81-93. See Lemma 29.

%H Igor Pak, <a href="https://arxiv.org/abs/1803.06636">Complexity problems in enumerative combinatorics</a>, arXiv:1803.06636 [math.CO], 2018.

%H John L. Pfaltz, <a href="http://virginia.edu/~jlp/partition.ps">Evaluating the binary partition function when N = 2^n</a>, Congr. Numer, 109:3-12, 1995. [Broken link]

%H B. Reznick, <a href="http://dx.doi.org/10.1007/978-1-4612-3464-7_29">Some binary partition functions</a>, in "Analytic number theory" (Conf. in honor P. T. Bateman, Allerton Park, IL, 1989), 451-477, Progr. Math., 85, Birkhäuser Boston, Boston, MA, 1990.

%H O. J. Rodseth, <a href="http://dx.doi.org/10.1016/j.disc.2006.02.010">Enumeration of M-partitions</a>, Discrete Math., 306 (2006), 694-698.

%H O. J. Rodseth and J. A. Sellers, <a href="http://dx.doi.org/10.1006/jcta.2001.3223">Binary partitions revisited</a>, J. Combinatorial Theory, Series A 98 (2002), 33-45.

%H O. J. Rodseth and J. A. Sellers, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL8/Sellers/sellers75.html">On a Restricted m-Non-Squashing Partition Function</a>, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.

%H D. Ruelle, <a href="http://www.ams.org/notices/200208/fea-ruelle.pdf">Dynamical zeta functions and transfer operators</a>, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.

%H F. Ruskey, <a href="https://web.archive.org/web/20170508233132/theory.cs.uvic.ca/inf/nump/BinaryPartition.html">Info on binary partitions</a>

%H N. J. A. Sloane and J. A. Sellers, <a href="https://arxiv.org/abs/math/0312418">On non-squashing partitions</a>, arXiv:math/0312418 [math.CO], 2003.

%H N. J. A. Sloane and J. A. Sellers, <a href="https://doi.org/10.1016/j.disc.2004.11.014">On non-squashing partitions</a>, Discrete Math., 294 (2005), 259-274.

%H Daniel G. Zhu, <a href="https://arxiv.org/abs/2402.10025">An improved lower bound on the Shannon capacities of complements of odd cycles</a>, arXiv:2402.10025 [math.CO], 2024.

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F a(n) = A018819(2*n).

%F a(n) = a(n-1) + a(floor(n/2)). For proof see A018819.

%F 2 * a(n) = a(n+1) + a(n-1) if n is even. - _Michael Somos_, Jan 07 2011

%F G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).

%F a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].

%F a(n) = (1/n)*Sum_{k=1..n} (A038712(k)+1)*a(n-k), n > 1, a(0)=1. - _Vladeta Jovovic_, Aug 22 2002

%F Conjecture: Limit_{n ->infinity} (log(n)*a(2n))/(n*a(n)) = c = 1.63... - _Benoit Cloitre_, Jan 26 2003 [The constant c is equal to 2*log(2) = 1.38629436... =A016627. - _Vaclav Kotesovec_, Aug 07 2019]

%F G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - _Michael Somos_, Aug 25 2003

%F G.f.: Product_{k>=0} (1+x^(2^k))/(1-x^(2^k)) = (Product_{k>=0} (1+x^(2^k))^(k+1) )/(1-x) = Product_{k>=0} (1+x^(2^k))^(k+2). - _Joerg Arndt_, Apr 24 2005

%F From _Philippe Flajolet_, Sep 06 2008: (Start)

%F The asymptotic rate of growth is known precisely - see De Bruijn's paper. With p(n) the number of partitions of n into powers of two, the asymptotic formula of de Bruijn is: log(p(2*n)) = 1/(2*L2)*(log(n/log(n)))^2 + (1/2 + 1/L2 + LL2/L2)*log(n) - (1 + LL2/L2)*log(log(n)) + Phi(log(n/log(n))/L2), where L2=log(2), LL2=log(log(2)) and Phi(x) is a certain periodic function with period 1 and a tiny amplitude.

%F Numerically, Phi(x) appears to have a mean value around 0.66. An expansion up to O(1) term had been obtained earlier by Kurt Mahler. (End)

%F G.f.: exp( Sum_{n>=1} 2^A001511(n) * x^n/n ), where 2^A001511(n) is the highest power of 2 that divides 2*n. - _Paul D. Hanna_, Oct 30 2012

%F (n/2)*a(n) = Sum_{k = 0..n-1} (n-k)/A000265(n-k)*a(k). - _Peter Bala_, Mar 03 2019

%e For non-squashing partitions and binary partitions see the example in A018819.

%e For n=3, the a(3)=6 admitted partitions of 2n=6 are 1+1+1+1+1+1, 1+1+1+1+2, 1+1+2+2, 2+2+2, 1+1+4 and 2+4. - _R. J. Mathar_, Aug 11 2021

%p A000123 := proc(n) option remember; if n=0 then 1 else A000123(n-1)+A000123(floor(n/2)); fi; end; [ seq(A000123(i),i=0..50) ];

%p # second Maple program: more efficient for large n; try: a( 10^25 );

%p g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or

%p n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)

%p *g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))

%p end:

%p a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):

%p seq(a(n), n=0..60); # _Alois P. Heinz_, Apr 16 2009, revised Apr 14 2016

%t a[0] = 1; a[n_] := a[n] = a[Floor[n/2]] + a[n-1]; Array[a,49,0] (* _Jean-François Alcover_, Apr 11 2011, after _M. F. Hasler_ *)

%t Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* _Birkas Gyorgy_, Apr 18 2011 *)

%o (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) / (1-x)); polcoeff(A, n))}; /* _Michael Somos_, Aug 25 2003 */

%o (PARI) {a(n) = if( n<1, n==0, a(n\2) + a(n-1))}; /* _Michael Somos_, Aug 25 2003 */

%o (PARI) A123=[];A000123(n)={ n<3 && return(2^n); if( n<=#A123, A123[n] && return(A123[n]); A123[n-1] && return( A123[n] = A123[n-1]+A000123(n\2) ), n>2*#A123 && A123=concat(A123,vector((n-#A123)\2))); A123[if(n>#A123,1,n)]=2*sum(k=1,n\2-1,A000123(k),1)+(n%2+1)*A000123(n\2)} \\ Stores results in global vector A123 dynamically resized to at most 3n/4 when size is less than n/2. Gives a(n*10^6) in ~ n sec. - _M. F. Hasler_, Apr 30 2009

%o (PARI) {a(n)=polcoeff(exp(sum(m=1,n,2^valuation(2*m,2)*x^m/m)+x*O(x^n)),n)} \\ _Paul D. Hanna_, Oct 30 2012

%o (Haskell)

%o import Data.List (transpose)

%o a000123 n = a000123_list !! n

%o a000123_list = 1 : zipWith (+)

%o a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])

%o -- _Reinhard Zumkeller_, Nov 15 2012, Aug 01 2011

%o (Magma) [1] cat [n eq 1 select n+1 else Self(n-1) + Self(n div 2): n in [1..70]]; // _Vincenzo Librandi_, Dec 17 2016

%o (Python)

%o from functools import lru_cache

%o @lru_cache(maxsize=None)

%o def A000123(n): return 1 if n == 0 else A000123(n-1) + A000123(n//2) # _Chai Wah Wu_, Jan 18 2022

%Y Cf. A000041, A002033, A002487, A002577, A005704-A005706, A023359, A040039, A100529. Partial sums and bisection of A018819.

%Y A column of A072170. Row sums of A089177. Twice A033485.

%Y Cf. A145515. - _Alois P. Heinz_, Apr 16 2009

%Y Cf. A171370. - _Gary W. Adamson_, Dec 06 2009

%K nonn,easy,core,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from Robin Trew (trew(AT)hcs.harvard.edu)

%E Values up to a(10^4) checked with given PARI code by _M. F. Hasler_, Apr 30 2009

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)