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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007178 Number of ways to write 1 as ordered sum of n powers of 1/2, allowing repeats.
(Formerly M2951)
11
1, 1, 3, 13, 75, 525, 4347, 41245, 441675, 5259885, 68958747, 986533053, 15292855019, 255321427725, 4567457001915, 87156877087069, 1767115200924299, 37936303950503853, 859663073472084315, 20505904049009202685, 513593410566661282347, 13476082013068430626893 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

REFERENCES

D. E. Knuth, personal communication.

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 = 1..300

A. Giorgilli, G. Molteni, Representation of a 2-power as sum of k 2-powers: a recursive formula, J. Number Theory 133 (2013), no. 4, 1251-1261.

D. E. Knuth, Letter to R. E. Tarjan & N. J. A. Sloane, Jul. 1975

Daniel Krenn and Stephan Wagner, Compositions into Powers of b : Asymptotic Enumeration and Parameters, arXiv:1410.4331 [math.NT], 2014.

S. Lehr, J. Shallit and J. Tromp, On the vector space of the automatic reals, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.

G. Molteni, Cancellation in a short exponential sum, J. Number Theory 130 (2010), no. 9, 2011-2027.

G. Molteni, Representation of a 2-power as sum of k 2-powers: the asymptotic behavior, Int. J. Number Theory 8 (2012), no. 8, 1923-1963.

FORMULA

a(n) = coefficient of z^(2^n) in (z+z^2+z^4+...+z^(2^n))^n. - Don Knuth.

From Giuseppe Molteni, Dec 14 2012: (Start)

(a(n)/n!)^{1/n} has a limit as n diverges, the limit is 1.192674341213466032221288982528755... (see References: "Representation of a 2-power as sum of k 2-powers: the asymptotic behavior").

a(n) = 4 + (-1)^n (mod 8) when n>2 (see References: "Representation of a 2-power as sum of k 2-powers: a recursive formula"). (End)

EXAMPLE

For n=3, the 3 sums are 1/2+1/4+1/4, 1/4+1/2+1/4, and 1/4+1/4+1/2.

MAPLE

b:= proc(n, r, p) option remember; `if`(n<r, 0,

      `if`(r=0, `if`(n=0, p!, 0), add(1/j!*

       b(n-j, 2*(r-j), p+j), j=0..min(n, r))))

    end:

a:= n-> b(n, 1, 0):

seq(a(n), n=1..23);  # Alois P. Heinz, Nov 07 2017

MATHEMATICA

f[n_] := Coefficient[Expand[Sum[z^(2^j), {j, n}]^n], z, 2^n]; Array[f, 20] (* Robert G. Wilson v, Apr 08 2012 *)

PROG

(PARI) f(n)={my(M); if(n>1, M=matrix(n, n); M[2, 1] = 1; for(k=3, n, for(l=1, k-2, M[k, l] = 0; smx = min(2*l, k-l-1); for(s=1, smx, M[k, l] += binomial(k+l-1, 2*l-s)*M[k-l, s])); M[k, k-1] = 1); M[n, 1], 1)}

CROSSREFS

Cf. A002572, A294746.

Sequence in context: A276894 A074517 A251658 * A173990 A276924 A276895

Adjacent sequences:  A007175 A007176 A007177 * A007179 A007180 A007181

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane , Simon Plouffe, Don Knuth

EXTENSIONS

More terms from Hugo van der Sanden

Minor edits, Vaclav Kotesovec, Jul 26 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 16 14:47 EST 2019. Contains 320163 sequences. (Running on oeis4.)