|
|
A000123
|
|
Number of binary partitions: number of partitions of 2n into powers of 2.
(Formerly M1011 N0378)
|
|
107
|
|
|
1, 2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, 202, 238, 284, 330, 390, 450, 524, 598, 692, 786, 900, 1014, 1154, 1294, 1460, 1626, 1828, 2030, 2268, 2506, 2790, 3074, 3404, 3734, 4124, 4514, 4964, 5414, 5938, 6462, 7060, 7658, 8350, 9042, 9828
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
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].
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
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
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
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
Sum over k <= n of number of partitions of k into powers of 2, A018819. - Peter Munn, Feb 21 2020
|
|
REFERENCES
|
G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976.
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.
N. G. de Bruijn, On Mahler's partition problem, Indagationes Mathematicae, vol. X (1948), 210-220.
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
H. Gupta, A simple proof of the Churchhouse conjecture concerning binary partitions, Indian J. Pure Appl. Math. 3 (1972), 791-794.
H. Gupta, A direct proof of the Churchhouse conjecture concerning binary partitions, Indian J. Math. 18 (1976), 1-5.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
M. D. Hirschhorn and J. A. Sellers, A different view of m-ary partitions, Australasian J. Combin., 30 (2004), 193-196.
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 86-91.
B. Reznick, Some binary partition functions, 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.
|
|
FORMULA
|
a(n) = a(n-1) + a(floor(n/2)). For proof see A018819.
2 * a(n) = a(n+1) + a(n-1) if n is even. - Michael Somos, Jan 07 2011
G.f.: (1-x)^(-1) Product_{n>=0} (1 - x^(2^n))^(-1).
a(n) = Sum_{i=0..n} a(floor(i/2)) [O'Shea].
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]
G.f. A(x) satisfies A(x^2) = ((1-x)/(1+x)) * A(x). - Michael Somos, Aug 25 2003
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
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.
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)
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
|
|
EXAMPLE
|
For non-squashing partitions and binary partitions see the example in A018819.
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
|
|
MAPLE
|
# second Maple program: more efficient for large n; try: a( 10^25 );
g:= proc(b, n) option remember; `if`(b<0, 0, `if`(b=0 or
n=0, 1, `if`(b>=n, add((-1)^(t+1)*binomial(n+1, t)
*g(b-t, n), t=1..n+1), g(b-1, n)+g(2*b, n-1))))
end:
a:= n-> (t-> g(n/2^(t-1), t))(max(ilog2(2*n), 1)):
seq(a(n), n=0..60); # Alois P. Heinz, Apr 16 2009, revised Apr 14 2016
|
|
MATHEMATICA
|
Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* Birkas Gyorgy, Apr 18 2011 *)
|
|
PROG
|
(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 */
(PARI) {a(n) = if( n<1, n==0, a(n\2) + a(n-1))}; /* Michael Somos, Aug 25 2003 */
(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
(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
(Haskell)
import Data.List (transpose)
a000123 n = a000123_list !! n
a000123_list = 1 : zipWith (+)
a000123_list (tail $ concat $ transpose [a000123_list, a000123_list])
(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
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Robin Trew (trew(AT)hcs.harvard.edu)
Values up to a(10^4) checked with given PARI code by M. F. Hasler, Apr 30 2009
|
|
STATUS
|
approved
|
|
|
|