|
| |
|
|
A000123
|
|
Number of binary partitions: number of partitions of 2n into powers of 2.
(Formerly M1011 N0378)
|
|
68
|
|
|
|
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]. [From Mats Granvik, 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.
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.
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.
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] (* From 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]] (* Gyorgy Birkas, 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 1 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
|
|
|
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. [From M. F. Hasler, Apr 30 2009]
|
|
|
STATUS
|
approved
|
| |
|
|
