login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A194628 Arises in enumerating Huffman codes, compact trees, and sums of unit fractions. 9
1, 1, 1, 2, 4, 8, 16, 31, 61, 121, 240, 476, 944, 1872, 3712, 7362, 14601, 28958, 57432, 113904, 225904, 448034, 888583, 1762321, 3495200, 6932008, 13748208, 27266738, 54077957, 107252486, 212713209, 421872826, 836697836, 1659417786, 3291113315, 6527245245, 12945446241, 25674625681 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,4
COMMENTS
a(n+1) is the number of compositions n=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 5*p(k+1), see example. - Joerg Arndt, Dec 18 2012
Row 4 of Table 1 of Elsholtz, row 1 being A002572, row 2 being A176485, and row 3 being A176503.
LINKS
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. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.
FORMULA
a(n) = A294775(n-1,4). - Alois P. Heinz, Nov 08 2017
EXAMPLE
From Joerg Arndt, Dec 18 2012: (Start)
There are a(6+1)=16 compositions 6=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 5*p(k+1):
[ 1] [ 1 1 1 1 1 1 ]
[ 2] [ 1 1 1 1 2 ]
[ 3] [ 1 1 1 2 1 ]
[ 4] [ 1 1 1 3 ]
[ 5] [ 1 1 2 1 1 ]
[ 6] [ 1 1 2 2 ]
[ 7] [ 1 1 3 1 ]
[ 8] [ 1 1 4 ]
[ 9] [ 1 2 1 1 1 ]
[10] [ 1 2 1 2 ]
[11] [ 1 2 2 1 ]
[12] [ 1 2 3 ]
[13] [ 1 3 1 1 ]
[14] [ 1 3 2 ]
[15] [ 1 4 1 ]
[16] [ 1 5 ]
(End)
MATHEMATICA
b[n_, r_, k_] := b[n, r, k] = If[n < r, 0, If[r == 0, If[n == 0, 1, 0], Sum[b[n - j, k (r - j), k], {j, 0, Min[n, r]}]]];
a[n_] := b[4n - 3, 1, 5];
Array[a, 40] (* Jean-François Alcover, Jul 21 2018, after Alois P. Heinz *)
PROG
(PARI) /* see A002572, set t=5 */
CROSSREFS
Sequence in context: A332726 A239557 A001591 * A003240 A280543 A282566
KEYWORD
nonn
AUTHOR
Jonathan Vos Post, Aug 30 2011
EXTENSIONS
Terms beyond a(20)=113904 added by Joerg Arndt, Dec 18 2012
Invalid empirical g.f. removed by Alois P. Heinz, Nov 08 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:58 EDT 2024. Contains 370952 sequences. (Running on oeis4.)