|
%I M0710 N0261 #122 Jan 15 2022 00:26:37
%S 1,1,1,2,3,5,9,16,28,50,89,159,285,510,914,1639,2938,5269,9451,16952,
%T 30410,54555,97871,175586,315016,565168,1013976,1819198,3263875,
%U 5855833,10506175,18849555,33818794,60675786,108861148,195312750,350419594,628704034,1127987211,2023774607,3630948907
%N Number of partitions of 1 into n powers of 1/2; or (according to one definition of "binary") the number of binary rooted trees.
%C This is similar to a question about Egyptian fractions, except that there the denominators of the fractions must be distinct. - _N. J. A. Sloane_, Jan 13 2021
%C Math. Rev. 22 #11020, Minc, H. A problem in partitions ... 1959: v(c, d) is the number of partitions of d into positive integers of the form d = c + c_1 + c_2 + ... + c_n, where c_1 <= 2*c, c_{i+1} <= 2*c_i.
%C Top row of Table 1 of Elsholtz. [_Jonathan Vos Post_, Aug 30 2011]
%C a(n+1) is the number of compositions n = p(1) + p(2) + ... + p(m) with p(1)=1 and p(k) <= 2*p(k+1), see example. [_Joerg Arndt_, Dec 18 2012]
%C Over an algebraically closed field of characteristic 2, a(n) gives dimensions of the generic cohomology groups H^i_gen(SL_2,L(1)) which are isomorphic to algebraic group cohomology groups H^i(SL_2,L(1)^[i]), where ^[i] denotes i-th Frobenius twist. [_David I. Stewart_, Oct 22 2013]
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 192-194, 307.
%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="/A002572/b002572.txt">Table of n, a(n) for n = 1..2000</a> (first 201 terms from T. D. Noe)
%H Christian Elsholtz, Clemens Heuberger, and Daniel Krenn, <a href="https://arxiv.org/abs/1901.11343">Algorithmic counting of nonequivalent compact Huffman codes</a>, arXiv:1901.11343 [math.CO], 2019.
%H Christian Elsholtz, Clemens Heuberger, and Helmut Prodinger, <a href="http://arxiv.org/abs/1108.5964">The number of Huffman codes, compact trees, and sums of unit fractions</a>, arXiv:1108.5964v1 [math.CO], Aug 30, 2011. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.
%H Shimon Even and Abraham Lempel, <a href="http://dx.doi.org/10.1016/S0019-9958(72)90149-0">Generation and enumeration of all solutions of the characteristic sum condition</a>, Information and Control 21 (1972), 476-482.
%H P. Flajolet and H. Prodinger, <a href="http://dx.doi.org/10.1016/0012-365X(87)90137-3">Level number sequences for trees</a>, Discrete Math., 65 (1987), 149-156.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 200
%H E. N. Gilbert, <a href="http://dx.doi.org/10.1109/TIT.1971.1054638">Codes based on inaccurate source probabilities</a>, IEEE Trans. Inform. Theory, 17 (1971), 304-315.
%H R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: <a href="/A002572/a002572.jpg">front</a>, <a href="/A002572/a002572_1.jpg">back</a> [Annotated scanned copy, with permission]
%H H. Minc, <a href="http://dx.doi.org/10.1017/S0013091500021945">A problem in partitions: Enumeration of elements of a given degree in the free commutative entropic cyclic groupoid</a>, Proc. Edinburgh Math. Soc. (2) 11 1958/1959 223-224.
%H E. Norwood, <a href="http://dx.doi.org/10.1109/TIT.1967.1054058">The Number of Different Possible Compact Codes</a>, IEEE Transactions on Information Theory, Vol. 13, P. 614, 1967.
%H J. Paschke et al., <a href="http://dx.doi.org/10.1016/j.disc.2010.08.017">Computing and estimating the number of n-ary Huffman sequences of a specified length</a>, Discrete Math., 311 (2011), 1-7. (See p. 3.)
%H Helmut Prodinger, <a href="https://arxiv.org/abs/2103.15791">Philippe Flajolet's early work in combinatorics</a>, arXiv:2103.15791 [math.CO], 2021.
%H N. J. A. Sloane, <a href="/A002572/a002572_3.pdf">Richard Guy and the Encyclopedia of Integer Sequences: A Fifty-Year Friendship</a>, Slides of talk at Conference "Celebrating Richard Guy", University of Calgary, October 2, 2020.
%H D. I. Stewart, <a href="http://dx.doi.org/10.1016/j.jalgebra.2012.04.026">Unbounding Ext</a>, J. Algebra, 365 (2012), 1-11. (See p. 7)
%H Paul R. Stein, <a href="/A002572/a002572.pdf">Letter to N. J. A. Sloane, Jul 20 1971</a>
%H Paul R. Stein, <a href="/A002572/a002572_1.pdf">Table of first 127 terms</a>
%H <a href="/index/Cor#core">Index entries for "core" sequences</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Ed#Egypt">Index entries for sequences related to Egyptian fractions</a>
%F From _Jon E. Schoenfield_, Dec 18 2016: (Start)
%F Numerically, it appears that
%F lim_{n->infinity} a(n)/c0^n = c1
%F and
%F lim_{n->infinity} (a(n)/c0^n - c1) / c2^n = c3
%F where
%F c0 = 1.79414718754168546349846498809380776370136441826513
%F 55647141291458811011534167435879115275875728251544
%F 55034381754309507738861994388752350104180891093803
%F 27324310643547892073673907996758374498542252887021
%F 90... = A102375
%F c1 = 0.14185320208540933707157739062733520381135377764439
%F 00938624762999524081108574037129602775796177848175
%F 96757823284956317508884467180902882086032012675483
%F 68631687927534330190816399081295424373415296405657
%F 19...
%F c2 = 0.71317957835995615685267138702642988919007297942329
%F 35...
%F c3 = 0.06124104103121269745282188448763211918477582400104
%F 06... (End)
%F a(n) = A294775(n-1,1). - _Alois P. Heinz_, Nov 08 2017
%e {1}; {1/2 + 1/2}; { 1/2 + 1/4 + 1/4 }; { 1/2 + 1/4 + 1/8 + 1/8, 1/4 + 1/4 + 1/4 + 1/4 }; ...
%e From _Joerg Arndt_, Dec 18 2012: (Start)
%e There are a(7+1)=16 compositions 7=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 2*p(k+1):
%e [ 1] [ 1 1 1 1 1 1 1 ]
%e [ 2] [ 1 1 1 1 1 2 ]
%e [ 3] [ 1 1 1 1 2 1 ]
%e [ 4] [ 1 1 1 2 1 1 ]
%e [ 5] [ 1 1 1 2 2 ]
%e [ 6] [ 1 1 2 1 1 1 ]
%e [ 7] [ 1 1 2 1 2 ]
%e [ 8] [ 1 1 2 2 1 ]
%e [ 9] [ 1 1 2 3 ]
%e [10] [ 1 2 1 1 1 1 ]
%e [11] [ 1 2 1 1 2 ]
%e [12] [ 1 2 1 2 1 ]
%e [13] [ 1 2 2 1 1 ]
%e [14] [ 1 2 2 2 ]
%e [15] [ 1 2 3 1 ]
%e [16] [ 1 2 4 ]
%e (End)
%e From _Joerg Arndt_, Dec 26 2012: (Start)
%e There are a(8)=16 partitions of 1 into 8 powers of 1/2 (dots denote zeros in the tables of multiplicities in the left column)
%e [ 1] [ . 1 1 1 1 1 1 2 ] + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 2/128
%e [ 2] [ . 1 1 1 1 . 4 . ] + 1/2 + 1/4 + 1/8 + 1/16 + 4/64
%e [ 3] [ . 1 1 1 . 3 2 . ] + 1/2 + 1/4 + 1/8 + 3/32 + 2/64
%e [ 4] [ . 1 1 . 3 1 2 . ] + 1/2 + 1/4 + 3/16 + 1/32 + 2/64
%e [ 5] [ . 1 1 . 2 4 . . ] + 1/2 + 1/4 + 2/16 + 4/32
%e [ 6] [ . 1 . 3 1 1 2 . ] + 1/2 + 3/8 + 1/16 + 1/32 + 2/64
%e [ 7] [ . 1 . 3 . 4 . . ] + 1/2 + 3/8 + 4/32
%e [ 8] [ . 1 . 2 3 2 . . ] + 1/2 + 2/8 + 3/16 + 2/32
%e [ 9] [ . 1 . 1 6 . . . ] + 1/2 + 1/8 + 6/16
%e [10] [ . . 3 1 1 1 2 . ] + 3/4 + 1/8 + 1/16 + 1/32 + 2/64
%e [11] [ . . 3 1 . 4 . . ] + 3/4 + 1/8 + 4/32
%e [12] [ . . 3 . 3 2 . . ] + 3/4 + 3/16 + 2/32
%e [13] [ . . 2 3 1 2 . . ] + 2/4 + 3/8 + 1/16 + 2/32
%e [14] [ . . 2 2 4 . . . ] + 2/4 + 2/8 + 4/16
%e [15] [ . . 1 5 2 . . . ] + 1/4 + 5/8 + 2/16
%e [16] [ . . . 8 . . . . ] + 8/8
%e (End)
%p v := proc(c,d) option remember; local i; if d < 0 or c < 0 then 0 elif d = c then 1 else add(v(i,d-c),i=1..2*c); fi; end; [ seq(v(1,n), n=1..50) ];
%t v[c_, d_] := v[c, d] = If[d < 0 || c < 0, 0, If[d == c, 1, Sum[v[i, d - c], {i, 1, 2*c}]]]; a[n_] := v[1, n-1]; a[1] = 1; Table[a[n], {n, 1, 36}] (* _Jean-François Alcover_, Oct 19 2011, after Maple *)
%o (PARI) v(c,d) = if ( d<0 || c<0, 0, if ( d==c, 1, sum(i=1,2*c, v(i,d-c) ) ) )
%o (PARI)
%o /* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */
%o N=66; q='q+O('q^N);
%o t=2; /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503 */
%o L=2 + 2*ceil( log(N) / log(t) );
%o f(k)=(1-t^k)/(1-t);
%o la(j)=prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) );
%o nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) );
%o dn=sum(j=0, L, (-1)^j * la(j) );
%o gf=nm / dn;
%o Vec( gf )
%o /* _Joerg Arndt_, Dec 27 2012 */
%o (PARI) {a(n, k=2) = if( n<2 && k==2, n>=0, n<k || k<1, 0, n==k, 1, sum(i=2, min(n-k+1, 2*k-1), a(n-k+1, i)))}; /* _Michael Somos_, Dec 20 2016 */
%Y Cf. A002573, A002574, A007178, A047913, A049284, A049285, A102375, A294775.
%K core,nonn,nice,easy
%O 1,4
%A _N. J. A. Sloane_
| 