|
%I M1239 N0473 #83 Mar 28 2019 00:50:00
%S 1,2,4,10,36,202,1828,27338,692004,30251722,2320518948,316359580362,
%T 77477180493604,34394869942983370,27893897106768940836,
%U 41603705003444309596874,114788185359199234852802340,588880400923055731115178072778,5642645813427132737155703265972004
%N Number of partitions of 2^n into powers of 2.
%C 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 the OEIS till now. - _Valentin Bakoev_, Feb 25 2009; edited by _M. F. Hasler_, Feb 09 2014
%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 Lawrence, Jim. "Dual-Antiprisms and Partitions of Powers of 2 into Powers of 2." Discrete & Computational Geometry, Vol. 16 (2019): 465-478. See page 466.
%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="/A002577/b002577.txt">Table of n, a(n) for n = 0..85</a>
%H V. Bakoev, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00096-7">Algorithmic approach to counting of certain types m-ary partitions</a>, Discrete Mathematics, 275 (2004) pp.17-41.
%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 G. Blom and C.-E. Froeberg, <a href="https://www.jstor.org/stable/24524798">Om myntvaexling</a>, (On money-changing) [ Swedish ], Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103.
%H G. Blom and C.-E. Froeberg, <a href="/A002575/a002575.pdf">Om myntvaexling (On money-changing) [Swedish]</a>, Nordisk Matematisk Tidskrift, 10 (1962), 55-69, 103. [Annotated scanned copy]
%H R. F. Churchhouse, <a href="http://dx.doi.org/10.1017/S0305004100045072">Congruence properties of the binary partition function</a>, Math. Proc. Cambr. Phil. Soc. vol 66, no. 2 (1969), 365-370.
%H Carl-Erik Froberg, <a href="http://dx.doi.org/10.1007/BF01933448">Accurate estimation of the number of binary partitions</a>, BIT Numerical Mathematics vol. 17, no 4 (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 H. Minc, <a href="https://doi.org/10.1017/S008045410003226X">The free commutative entropic logarithmetic</a>, Proc. Roy. Soc. Edinburgh Sect. A 65 1959 177-192 (1959).
%F 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
%F a(n) = A078121(n+1, 1). - _Paul D. Hanna_, Sep 13 2004
%F 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_, Feb 25 2009
%F a(n) = [x^(2^n)] 1/Product_{j>=0} (1-x^(2^j)). - _Alois P. Heinz_, Sep 27 2011
%e 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_, Feb 25 2009]
%e G.f. = 1 + 2*x + 4*x^2 + 10*x^3 + 36*x^4 + 202*x^5 + 1828*x^6 + ...
%p A002577 := proc(n) if n<=1 then n+1 else A000123(2^(n-1)); fi; end;
%t $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 *)
%t a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^2^k, {k, 0, n}], {x, 0, 2^n}]; (* _Michael Somos_, Apr 21 2014 *)
%o (PARI) a(n)=polcoeff(prod(j=0,n,1/(1-x^(2^j)+x*O(x^(2^n)))),2^n) \\ _Paul D. Hanna_
%o (Haskell)
%o import Data.MemoCombinators (memo2, list, integral)
%o a002577 n = a002577_list !! n
%o a002577_list = f [1] where
%o f xs = (p' xs $ last xs) : f (1 : map (* 2) xs)
%o p' = memo2 (list integral) integral p
%o p _ 0 = 1; p [] _ = 0
%o p ks'@(k:ks) m = if m < k then 0 else p' ks' (m - k) + p' ks m
%o -- _Reinhard Zumkeller_, Nov 27 2015
%Y a(n) = A000123(2^(n-1)) = A018818(2^n).
%Y Cf. A078537, A078121, A000290, A000447.
%Y Column k=2 of A145515, diagonal of A152977. - _Alois P. Heinz_, Mar 25 2012
%Y See also A002575, A002576.
%Y A column of A125790.
%Y Cf. A000079, A078125, A145513.
%K nonn,easy,nice
%O 0,2
%A _N. J. A. Sloane_
%E Edited by _M. F. Hasler_, Feb 09 2014
|
