|
| |
|
|
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)
|
|
22
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,4
|
|
|
COMMENTS
| Top row of Table 1 of Elsholtz.
|
|
|
REFERENCES
| Christian Elsholtz, Clemens Heuberger, 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 [Jonathan Vos Post, Aug 30 2011].
S. Even and A. 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.
E. N. Gilbert, Codes based on inaccurate source probabilities, IEEE Trans. Inform. Theory, 17 (1971), 304-315.
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.)
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).
P. R. Stein, personal communication.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n = 1..201
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 200
Index entries for "core" sequences
Index entries for sequences related to trees
Index entries for sequences related to rooted trees
|
|
|
FORMULA
| 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.
|
|
|
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 }; ...
|
|
|
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}] (* From 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) ) ) )
|
|
|
CROSSREFS
| Cf. A002573, A047913, A002574, A049284, A049285, A007178.
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 (njas(AT)research.att.com).
|
| |
|
|
