A194628 Arises in enumerating Huffman codes, compact trees, and sums of unit fractions.

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

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

Alois P. Heinz, Table of n, a(n) for n = 1..1000

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

Cf. A002572, A176485, A176503, A294775.

Sequence in context: A332726 A239557 A001591 * A003240 A378698 A280543

Adjacent sequences: A194625 A194626 A194627 * A194629 A194630 A194631

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