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

1, 1, 1, 2, 4, 8, 16, 32, 64, 128, 255, 509, 1017, 2032, 4060, 8112, 16208, 32384, 64704, 129280, 258304, 516098, 1031177, 2060318, 4116568, 8225008, 16433776, 32835104, 65605376, 131081216, 261903618, 523290119, 1045547025, 2089029664, 4173934632, 8339628016

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) <= 8*p(k+1). - Joerg Arndt, Dec 18 2012

Row 7 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, and row 6 being A194630.

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,7). - Alois P. Heinz, Nov 08 2017

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

Prog

(PARI) /* see A002572, set t=8 */

Crossrefs

Cf. A002572, A176485, A176503, A194628, A194629, A194630, A294775.

Sequence in context: A172317 A234589 A079262 * A251746 A251760 A243086

Adjacent sequences: A194628 A194629 A194630 * A194632 A194633 A194634

Keyword

nonn

Author

Jonathan Vos Post, Aug 30 2011

Extensions

Terms beyond a(20)=129280 added by Joerg Arndt, Dec 18 2012

Status

approved