cp's OEIS Frontend

A007178 Number of ways to write 1 as ordered sum of n powers of 1/2, allowing repeats.

%I A007178 M2951 #63 Feb 02 2024 09:06:41
%S A007178 1,1,3,13,75,525,4347,41245,441675,5259885,68958747,986533053,
%T A007178 15292855019,255321427725,4567457001915,87156877087069,
%U A007178 1767115200924299,37936303950503853,859663073472084315,20505904049009202685,513593410566661282347,13476082013068430626893
%N A007178 Number of ways to write 1 as ordered sum of n powers of 1/2, allowing repeats.
%C A007178 Also the dimension of the arity n component of the operad of level algebras (see the reference by Chataur-Livernet by definition), and the cardinality of the subset of the free commutative medial magma with n generators that contains each generator exactly once. The linear operad of level algebras is the linearization of the set operad of commutative medial magmas; the statement about commutative medial magmas follows from the description in the paper of Ježek-Kepka. - _Vladimir Dotsenko_, Mar 12 2022
%D A007178 D. E. Knuth, personal communication.
%D A007178 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A007178 Alois P. Heinz, <a href="/A007178/b007178.txt">Table of n, a(n) for n = 1..300</a>
%H A007178 D. Chataur and M. Livernet, <a href="https://arxiv.org/abs/math/0209363">Adem-Cartan operads</a>, arXiv:math/0209363 [math.AT], 2002-2003; Communications in Algebra 33 (2005), 4337-4360.
%H A007178 A. Giorgilli and G. Molteni, <a href="http://dx.doi.org/10.1016/j.jnt.2012.09.013">Representation of a 2-power as sum of k 2-powers: a recursive formula</a>, J. Number Theory 133 (2013), no. 4, 1251-1261.
%H A007178 Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 18.
%H A007178 J. Ježek and T. Kepka, <a href="http://dml.mathdoc.fr/item/106070/">Free entropic groupoids</a>, Commentationes Mathematicae Universitatis Carolinae,Tome 022 (1981), p. 223-233.
%H A007178 D. E. Knuth, <a href="/A007178/a007178.pdf">Letter to R. E. Tarjan & N. J. A. Sloane, Jul. 1975</a>
%H A007178 Daniel Krenn and Stephan Wagner, <a href="http://arxiv.org/abs/1410.4331">Compositions into Powers of b : Asymptotic Enumeration and Parameters</a>, arXiv:1410.4331 [math.NT], 2014.
%H A007178 S. Lehr, J. Shallit and J. Tromp, <a href="http://dx.doi.org/10.1016/0304-3975(95)00234-0">On the vector space of the automatic reals</a>, Theoret. Comput. Sci. 163 (1996), no. 1-2, 193-210.
%H A007178 G. Molteni, <a href="http://dx.doi.org/10.1016/j.jnt.2010.03.002">Cancellation in a short exponential sum</a>, J. Number Theory 130 (2010), no. 9, 2011-2027.
%H A007178 G. Molteni, <a href="http://dx.doi.org/10.1142/S1793042112501096">Representation of a 2-power as sum of k 2-powers: the asymptotic behavior</a>, Int. J. Number Theory 8 (2012), no. 8, 1923-1963.
%F A007178 a(n) = coefficient of z^(2^n) in (z+z^2+z^4+...+z^(2^n))^n. - _Don Knuth_.
%F A007178 From _Giuseppe Molteni_, Dec 14 2012: (Start)
%F A007178 Limit_{n->oo} (a(n)/n!)^(1/n) = 1.192674341213466032221288982528755... (see References: "Representation of a 2-power as sum of k 2-powers: the asymptotic behavior").
%F A007178 a(n) == 4 + (-1)^n (mod 8) for n > 2 (see References: "Representation of a 2-power as sum of k 2-powers: a recursive formula"). (End)
%F A007178 More precise asymptotics: a(n) ~ c * d^n * n!, where d = 1.192674341213466032221288982528755176734489232027131552652821007498903522051783..., c = 0.24849369086953813603231092781945750388624874631949260927875431616785914609... - _Vaclav Kotesovec_, Sep 20 2019
%F A007178 a(n) = A323840(n,n). - _Alois P. Heinz_, Mar 31 2021
%e A007178 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.
%p A007178 b:= proc(n, r, p) option remember; `if`(n<r, 0,
%p A007178       `if`(r=0, `if`(n=0, p!, 0), add(1/j!*
%p A007178        b(n-j, 2*(r-j), p+j), j=0..min(n, r))))
%p A007178     end:
%p A007178 a:= n-> b(n, 1, 0):
%p A007178 seq(a(n), n=1..23);  # _Alois P. Heinz_, Nov 07 2017
%t A007178 f[n_] := Coefficient[Expand[Sum[z^(2^j), {j, n}]^n], z, 2^n]; Array[f, 20] (* _Robert G. Wilson v_, Apr 08 2012 *)
%o A007178 (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)}
%Y A007178 Cf. A002572, A294746, A323840.
%K A007178 nonn,easy,nice
%O A007178 1,3
%A A007178 _N. J. A. Sloane_, _Simon Plouffe_, _Don Knuth_
%E A007178 More terms from _Hugo van der Sanden_
%E A007178 Minor edits from _Vaclav Kotesovec_, Jul 26 2014