login
Number of ways to write 1 as ordered sum of n powers of 1/2, allowing repeats.
(Formerly M2951)
13

%I M2951 #63 Feb 02 2024 09:06:41

%S 1,1,3,13,75,525,4347,41245,441675,5259885,68958747,986533053,

%T 15292855019,255321427725,4567457001915,87156877087069,

%U 1767115200924299,37936303950503853,859663073472084315,20505904049009202685,513593410566661282347,13476082013068430626893

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

%C 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 D. E. Knuth, personal communication.

%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="/A007178/b007178.txt">Table of n, a(n) for n = 1..300</a>

%H 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 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 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 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 D. E. Knuth, <a href="/A007178/a007178.pdf">Letter to R. E. Tarjan & N. J. A. Sloane, Jul. 1975</a>

%H 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 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 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 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 a(n) = coefficient of z^(2^n) in (z+z^2+z^4+...+z^(2^n))^n. - _Don Knuth_.

%F From _Giuseppe Molteni_, Dec 14 2012: (Start)

%F 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 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 More precise asymptotics: a(n) ~ c * d^n * n!, where d = 1.192674341213466032221288982528755176734489232027131552652821007498903522051783..., c = 0.24849369086953813603231092781945750388624874631949260927875431616785914609... - _Vaclav Kotesovec_, Sep 20 2019

%F a(n) = A323840(n,n). - _Alois P. Heinz_, Mar 31 2021

%e 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 b:= proc(n, r, p) option remember; `if`(n<r, 0,

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

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

%p end:

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

%p seq(a(n), n=1..23); # _Alois P. Heinz_, Nov 07 2017

%t 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 (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 Cf. A002572, A294746, A323840.

%K nonn,easy,nice

%O 1,3

%A _N. J. A. Sloane_, _Simon Plouffe_, _Don Knuth_

%E More terms from _Hugo van der Sanden_

%E Minor edits from _Vaclav Kotesovec_, Jul 26 2014