|
|
A002572
|
|
Number of partitions of 1 into n powers of 1/2; or (according to one definition of "binary") the number of binary rooted trees.
(Formerly M0710 N0261)
|
|
40
|
|
|
1, 1, 1, 2, 3, 5, 9, 16, 28, 50, 89, 159, 285, 510, 914, 1639, 2938, 5269, 9451, 16952, 30410, 54555, 97871, 175586, 315016, 565168, 1013976, 1819198, 3263875, 5855833, 10506175, 18849555, 33818794, 60675786, 108861148, 195312750, 350419594, 628704034, 1127987211, 2023774607, 3630948907
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
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
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.
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]
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]
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 192-194, 307.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Christian Elsholtz, Clemens Heuberger, and Helmut Prodinger, The number of Huffman codes, compact trees, and sums of unit fractions, arXiv:1108.5964v1 [math.CO], Aug 30, 2011. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.
R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]
D. I. Stewart, Unbounding Ext, J. Algebra, 365 (2012), 1-11. (See p. 7)
|
|
FORMULA
|
Numerically, it appears that
lim_{n->infinity} a(n)/c0^n = c1
and
lim_{n->infinity} (a(n)/c0^n - c1) / c2^n = c3
where
c0 = 1.79414718754168546349846498809380776370136441826513
55647141291458811011534167435879115275875728251544
55034381754309507738861994388752350104180891093803
27324310643547892073673907996758374498542252887021
c1 = 0.14185320208540933707157739062733520381135377764439
00938624762999524081108574037129602775796177848175
96757823284956317508884467180902882086032012675483
68631687927534330190816399081295424373415296405657
19...
c2 = 0.71317957835995615685267138702642988919007297942329
35...
c3 = 0.06124104103121269745282188448763211918477582400104
06... (End)
|
|
EXAMPLE
|
{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 }; ...
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):
[ 1] [ 1 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 1 2 ]
[ 3] [ 1 1 1 1 2 1 ]
[ 4] [ 1 1 1 2 1 1 ]
[ 5] [ 1 1 1 2 2 ]
[ 6] [ 1 1 2 1 1 1 ]
[ 7] [ 1 1 2 1 2 ]
[ 8] [ 1 1 2 2 1 ]
[ 9] [ 1 1 2 3 ]
[10] [ 1 2 1 1 1 1 ]
[11] [ 1 2 1 1 2 ]
[12] [ 1 2 1 2 1 ]
[13] [ 1 2 2 1 1 ]
[14] [ 1 2 2 2 ]
[15] [ 1 2 3 1 ]
[16] [ 1 2 4 ]
(End)
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)
[ 1] [ . 1 1 1 1 1 1 2 ] + 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + 2/128
[ 2] [ . 1 1 1 1 . 4 . ] + 1/2 + 1/4 + 1/8 + 1/16 + 4/64
[ 3] [ . 1 1 1 . 3 2 . ] + 1/2 + 1/4 + 1/8 + 3/32 + 2/64
[ 4] [ . 1 1 . 3 1 2 . ] + 1/2 + 1/4 + 3/16 + 1/32 + 2/64
[ 5] [ . 1 1 . 2 4 . . ] + 1/2 + 1/4 + 2/16 + 4/32
[ 6] [ . 1 . 3 1 1 2 . ] + 1/2 + 3/8 + 1/16 + 1/32 + 2/64
[ 7] [ . 1 . 3 . 4 . . ] + 1/2 + 3/8 + 4/32
[ 8] [ . 1 . 2 3 2 . . ] + 1/2 + 2/8 + 3/16 + 2/32
[ 9] [ . 1 . 1 6 . . . ] + 1/2 + 1/8 + 6/16
[10] [ . . 3 1 1 1 2 . ] + 3/4 + 1/8 + 1/16 + 1/32 + 2/64
[11] [ . . 3 1 . 4 . . ] + 3/4 + 1/8 + 4/32
[12] [ . . 3 . 3 2 . . ] + 3/4 + 3/16 + 2/32
[13] [ . . 2 3 1 2 . . ] + 2/4 + 3/8 + 1/16 + 2/32
[14] [ . . 2 2 4 . . . ] + 2/4 + 2/8 + 4/16
[15] [ . . 1 5 2 . . . ] + 1/4 + 5/8 + 2/16
[16] [ . . . 8 . . . . ] + 8/8
(End)
|
|
MAPLE
|
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) ];
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI) v(c, d) = if ( d<0 || c<0, 0, if ( d==c, 1, sum(i=1, 2*c, v(i, d-c) ) ) )
(PARI)
/* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */
N=66; q='q+O('q^N);
L=2 + 2*ceil( log(N) / log(t) );
f(k)=(1-t^k)/(1-t);
la(j)=prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) );
nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) );
dn=sum(j=0, L, (-1)^j * la(j) );
gf=nm / dn;
Vec( gf )
(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 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
core,nonn,nice,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|