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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002577 Number of partitions of 2^n into powers of 2.
(Formerly M1239 N0473)
36
1, 2, 4, 10, 36, 202, 1828, 27338, 692004, 30251722, 2320518948, 316359580362, 77477180493604, 34394869942983370, 27893897106768940836, 41603705003444309596874, 114788185359199234852802340, 588880400923055731115178072778, 5642645813427132737155703265972004 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

For given m, the general formula for t_m(n, k) and the corresponding tables T, computed as in the example, determine a family of related sequences (placed in the rows or in the columns of T). For example, the numbers from the second row of T, computed for given m and n>2, are the (m+2)-gonal numbers. So the second row contains the first members of: A000290 (the square numbers) when m=2, A000326 (the pentagonal numbers) when m=3, and so on. But rows IV, V etc. of the given table are not represented in OEIS till now. - Valentin Bakoev (v_bakoev(AT)yahoo.com), Feb 25 2009; edited by M. F. Hasler, Feb 09 2014

REFERENCES

V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41. [From Valentin Bakoev (v_bakoev(AT)yahoo.com), Feb 25 2009]

G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [ Swedish ], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103.

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.

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

H. Minc, The free commutative entropic logarithmetic. Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).

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

Alois P. Heinz, Table of n, a(n) for n = 0..85

V. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp.17-41.

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, 2012. - From N. J. A. Sloane, Dec 23 2012

G. Blom and C.-E. Froeberg, Om myntvaexling (On money-changing) [Swedish], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy]

R. F. Churchhouse, Congruence properties of the binary partition function, Math. Proc. Cambr. Phil. Soc. vol 66, no. 2 (1969), 365-370.

Carl-Erik Froberg, Accurate estimation of the number of binary partitions, BIT Numerical Mathematics vol. 17, no 4 (1977) 386-391.

C.-E. Froberg, Accurate estimation of the number of binary partitions [Annotated scanned copy]

FORMULA

a(n) is about 0.9233*sum_j {i=0, 1, 2, 3, ...} 2^(j*(2n-j-1)/2)/j!. - Henry Bottomley, Jul 23 2003

a(n) = A078121(n+1, 1). - Paul D. Hanna, Sep 13 2004

A002577(n)-1 = A125792(n). - Let m > 1, n > 0 and k >= 0. The general formula for the number of all partitions of k.m^n into powers of m is: t_m(n, k)= k+1 if n=1, t_m(n, k)= 1 if k=0, and t_m(n, k)= t_m(n, k-1) + t_m(n-1, k.m) if n>1 and k>0. A002577 is obtained for m=2 and n=1,2,3,... - Valentin Bakoev (v_bakoev(AT)yahoo.com), Feb 25 2009

a(n) = [x^(2^n)] 1/Product_{j>=0}(1-x^(2^j)). - Alois P. Heinz, Sep 27 2011

EXAMPLE

To compute t_2(6,1) we can use a table T, defined as T[i,j]= t_2(i,j), for i=1,2,...,6(=n), and j= 0,1,2,...,32(= k.m^{n-1}). It is: 1,2,3,4,5,6,7,8,9...,33; 1,4,9,16,25,36,49...,81; (so the second row contains the first members of A000290 - the square numbers) 1,10,35,84,165,...,969; (so the third row contains the first members of A000447. The r-th tetrahedral number is given by formula r(r+1)(r+2)/6. This row (also A000447) contains the tetrahedral numbers, obtained for r=1,3,5,7,...) 1,36,201,656,1625; 1,202,1827; 1,1828; Column 1 contains the first 6 members of A002577. [Valentin Bakoev (v_bakoev(AT)yahoo.com), Feb 25 2009]

G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 36*x^4 + 202*x^5 + 1828*x^6 + ...

MAPLE

A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;

MATHEMATICA

$RecursionLimit = 10^5; (* b = A000123 *) b[0] = 1; b[n_?EvenQ] := b[n] = b[n-1] + b[n/2]; b[n_?OddQ] := b[n] = b[n-1] + b[(n-1)/2]; a[n_] := b[2^(n-1)]; a[0] = 1; Table[a[n], {n, 0, 17}] (* Jean-Fran├žois Alcover, Nov 23 2011 *)

a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^2^k, {k, 0, n}], {x, 0, 2^n}]; (* Michael Somos, Apr 21 2014 *)

PROG

(PARI) a(n)=polcoeff(prod(j=0, n, 1/(1-x^(2^j)+x*O(x^(2^n)))), 2^n) \\ Paul D. Hanna

(Haskell)

import Data.MemoCombinators (memo2, list, integral)

a002577 n = a002577_list !! n

a002577_list = f [1] where

   f xs = (p' xs $ last xs) : f (1 : map (* 2) xs)

   p' = memo2 (list integral) integral p

   p _ 0 = 1; p [] _ = 0

   p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m

-- Reinhard Zumkeller, Nov 27 2015

CROSSREFS

a(n) = A000123(2^(n-1)) = A018818(2^n).

Cf. A078537, A078121, A000290, A000447.

Column k=2 of A145515, diagonal of A152977. - Alois P. Heinz, Mar 25 2012

See also A002575, A002576.

A column of A125790.

Cf. A000079, A078125, A145513.

Sequence in context: A210777 A210778 A210779 * A076132 A047142 A081080

Adjacent sequences:  A002574 A002575 A002576 * A002578 A002579 A002580

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Edited by M. F. Hasler, Feb 09 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 14:52 EDT 2017. Contains 288790 sequences.