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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)
37
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

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.

Top row of Table 1 of Elsholtz. [Jonathan Vos Post, Aug 30 2011]

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

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

Alois P. Heinz, Table of n, a(n) for n = 1..2000 (first 201 terms from T. D. Noe)

Christian Elsholtz, Clemens Heuberger, Helmut Prodinger, The number of Huffman codes, compact trees, and sums of unit fractions, arXiv:1108.5964v1 [math.CO], Aug 30, 2011

Shimon Even & Abraham Lempel, Generation and enumeration of all solutions of the characteristic sum condition, Information and Control 21 (1972), 476-482.

P. Flajolet and H. Prodinger, Level number sequences for trees, Discrete Math., 65 (1987), 149-156.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 200

E. N. Gilbert, Codes based on inaccurate source probabilities, IEEE Trans. Inform. Theory, 17 (1971), 304-315.

R. K. Guy, Letter to N. J. A. Sloane, June 24 1971: front, back [Annotated scanned copy, with permission]

H. Minc, A problem in partitions: Enumeration of elements of a given degree in the free commutative entropic cyclic groupoid, Proc. Edinburgh Math. Soc. (2) 11 1958/1959 223-224.

E. Norwood, The Number of Different Possible Compact Codes, IEEE Transactions on Information Theory, Vol. 13, P. 614, 1967.

J. Paschke et al., Computing and estimating the number of n-ary Huffman sequences of a specified length, Discrete Math., 311 (2011), 1-7. (See p. 3.)

D. I. Stewart, Unbounding Ext, J. Algebra, 365 (2012), 1-11. (See p. 7)

Paul R. Stein, Letter to N. J. A. Sloane, Jul 20 1971

Paul R. Stein, Table of first 127 terms

Index entries for "core" sequences

Index entries for sequences related to trees

Index entries for sequences related to rooted trees

FORMULA

From Jon E. Schoenfield, Dec 18 2016: (Start)

Numerically, it appears that

     lim_{n->inf} a(n)/c0^n = c1

  and

     lim_{n->inf} (a(n)/c0^n - c1) / c2^n = c3

where

c0 = 1.79414718754168546349846498809380776370136441826513

       55647141291458811011534167435879115275875728251544

       55034381754309507738861994388752350104180891093803

       27324310643547892073673907996758374498542252887021

       90... = A102375

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 }; ...

From Joerg Arndt, Dec 18 2012: (Start)

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)

From Joerg Arndt, Dec 26 2012: (Start)

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);

t=2;  /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503  */

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 )

/* Joerg Arndt, Dec 27 2012 */

(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

Cf. A002573, A002574, A007178, A047913, A049284, A049285, A102375.

Sequence in context: A005314 A099529 A088352 * A114834 A143961 A128023

Adjacent sequences:  A002569 A002570 A002571 * A002573 A002574 A002575

KEYWORD

core,nonn,nice,easy

AUTHOR

N. J. A. Sloane

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 23 22:23 EDT 2017. Contains 291021 sequences.