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

1, 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2045, 4089, 8176, 16348, 32688, 65360, 130688, 261312, 522496, 1044736, 2088960, 4176896, 8351746, 16699401, 33390622, 66764888, 133497072, 266928752, 533726752, 1067192064, 2133861376, 4266677504, 8531265024

Offset: 1

Author

Jonathan Vos Post, Aug 30 2011

Keywords

• nonn

Comments

a(n+1) is the number of compositions n=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 10*p(k+1). [Joerg Arndt, Dec 18 2012]

Row 9 of Table 1 of Elsholtz, row 1 being A002572, row 2 being A176485, row 3 being A176503, row 4 being A194628, row 5 being A194629, row 6 being A194630, row 7 being A194631, and row 8 being A194632.

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.5964 [math.CO], Aug 30, 2011. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.

Crossrefs

Cf. A002572, A176485, A176503, A194628 - A194632, A294775.

Programs

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[9n-8, 1, 10];
Array[a, 40] (* Jean-François Alcover, Jul 21 2018, after Alois P. Heinz *)

PARI

/* see A002572, set t=10 */

Formula

a(n) = A294775(n-1,9).

Extensions

Added terms beyond a(20)=130688, Joerg Arndt, Dec 18 2012

Invalid empirical g.f. removed by Alois P. Heinz, Nov 08 2017