login
This site is supported by donations to The OEIS Foundation.

 

Logo

Many excellent designs for a new banner were submitted. We will use the best of them in rotation.

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)
69
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 (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].

Row sums of A101566. - Paul Barry, Jan 03 2005

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..inf.} 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

REFERENCES

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

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

R. F. Churchhouse, Congruence properties of the binary partition function. Proc. Cambridge Philos. Soc. 66 1969 371-376.

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.

C.-E. Froberg, Accurate estimation of the number of binary partitions, Nordisk Tidskr. Informationsbehandling (BIT) 17 (1977), 386-391.

H. Gupta, Proof of the Churchhouse conjecture concerning binary partitions, Proc. Camb. Phil. Soc. 70 (1971), 53-56.

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.

K. Ji and H. S. Wilf, Extreme palindromes, Amer. Math. Monthly, 115, no. 5 (2008), 447-451.

D. E. Knuth, An almost linear recurrence, Fib. Quart., 4 (1966), 117-128.

M. Konvalinka and I. Pak, Cayley compositions, partitions, polytopes, and geometric bijections, http://www.math.ucla.edu/~pak/papers/CayleyComp4.pdf. - From N. J. A. Sloane, Dec 22 2012

K. Mahler, On a special functional equation, Journ. London Math. Soc. 15 (1940), 115-123.

E. O'Shea, M-partitions: optimal partitions of weight for one scale pan, Discrete Math. 289 (2004), 81-93. See Lemma 29.

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, Birkhaeuser Boston, Boston, MA, 1990.

O. J. Rodseth, Enumeration of M-partitions, Discrete Math., 306 (2006), 694-698.

O. J. Rodseth and J. A. Sellers, Binary partitions revisited, J. Combinatorial Theory, Series A 98 (2002), 33-45.

D. Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.

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

T. D. Noe, Table of n, a(n) for n = 0..10000

Joerg Arndt, Fxtbook, p.728

H. Bottomley, Illustration of initial terms

P. Dumas and P. Flajolet, Asymptotique des recurrences mahleriennes: le cas cyclotomique, Journal de Theorie des Nombres de Bordeaux 8 (1996), pp. 1-30.

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

M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.

John L. Pfaltz, Evaluating the binary partition function when N = 2^n, Congr. Numer, 109:3-12, 1995.

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.

F. Ruskey, Info on binary partitions

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

Index entries for "core" sequences

FORMULA

a(n)=a(n-1)+a([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..inf} (1 - x^(2^n))^(-1).

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

a(n)=(1/n)*Sum_{k=1..n} (A038712(k)+1)*a(n-k), n > 1, a(0)=1. - Vladeta Jovovic, Aug 22 2002

Conjecture: lim n ->infinity (log(n)*a(2n))/(n*a(n)) = c = 1.63... - Benoit Cloitre, Jan 26 2003

G.f. A(x) satisfies A(x^2)=((1-x)/(1+x))A(x). - Michael Somos, Aug 25 2003

G.F.: prod(k=0, inf, (1+x^(2^k))/(1-x^(2^k)), or prod(k=0, inf, 1+x^(2^k))^(k+1))/(1-x), or prod(k=0, inf, (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. - Philippe Flajolet, Sep 06 2008

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.

MAPLE

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) ];

g:= proc(b, n) option remember; local t; if b<0 then 0 elif b=0 or n=0 then 1 elif b>=n then add (g(b-t, n) *binomial (n+1, t) *(-1)^(t+1), t=1..n+1) else g(b-1, n) +g(2*b, n-1) fi end: a:= proc(n) local t; t:= nops (convert (n, base, 2)); g(n /2^(t-1), t) end: seq (a(n), n=0..60);

## more efficient for large n; try: a( 10^14 );

## Alois P. Heinz, Apr 16 2009

MATHEMATICA

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 *)

Fold[Append[#1, Total[Take[Flatten[Transpose[{#1, #1}]], #2]]] &, {1}, Range[2, 49]] (* Birkas Gyorgy, Apr 18 2011 *)

PROG

(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)/(1-x)); polcoeff(A, n))

(PARI) a(n)=if(n<1, n==0, a(n\2)+a(n-1))

(PARI) a(n)={ n<3 & return(1<<n); if( n<=#A123, A123[n] & return(A123[n]); A123[n-1] & return( A123[n] = A123[n-1]+a(n\2) ), n>2*#A123 & A123=vector(n\2)); A123[ if(n<=#A123, n, 1) ]=2*sum(k=1, n\2-1, a(k), 1)+(n%2+1)*a(n\2) }

/* allocates a global vector A123 of size n/2. Gives a(n*10^6) in ~ n sec */

/* M. F. Hasler, Apr 30 2009 */

(Haskell)

import Data.List (transpose)

a000123 n = a000123_list !! n

a000123_list = 1 : zipWith (+)

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

-- Reinhard Zumkeller, Nov 15 2012, Aug 01 2011

(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

CROSSREFS

Cf. A000041, A002577, A005704, A005705, A005706, A018819, A023359, A040039, A002487.

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

Cf. A002033, A100529.

Cf. A145515. - Alois P. Heinz, Apr 16 2009

Cf. A171370. - Gary W. Adamson, Dec 06 2009

Sequence in context: A001307 A088932 A088954 * A103257 A103259 A082380

Adjacent sequences:  A000120 A000121 A000122 * A000124 A000125 A000126

KEYWORD

nonn,easy,core,nice,changed

AUTHOR

N. J. A. Sloane

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

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

Content is available under The OEIS End-User License Agreement .

Last modified April 18 06:38 EDT 2014. Contains 240704 sequences.