A176452 -id:A176452 - cp's OEIS frontend

A176485 First column of triangle in A176452.

1, 1, 1, 2, 4, 7, 13, 25, 48, 92, 176, 338, 649, 1246, 2392, 4594, 8823, 16945, 32545, 62509, 120060, 230598, 442910, 850701, 1633948, 3138339, 6027842, 11577747, 22237515, 42711863, 82037200, 157569867, 302646401, 581296715, 1116503866, 2144482948, 4118935248, 7911290530

Offset: 1

N. J. A. Sloane, Dec 07 2010

nonn

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

Row 2 of Table 1 of Elsholtz, row 1 being A002572. - Jonathan Vos Post, Aug 30 2011

			From _Joerg Arndt_, Dec 18 2012: (Start)
There are a(7+1)=25 compositions 7=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 3*p(k+1):
[ 1]  [ 1 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 1 2 ]
[ 3]  [ 1 1 1 1 2 1 ]
[ 4]  [ 1 1 1 1 3 ]
[ 5]  [ 1 1 1 2 1 1 ]
[ 6]  [ 1 1 1 2 2 ]
[ 7]  [ 1 1 1 3 1 ]
[ 8]  [ 1 1 2 1 1 1 ]
[ 9]  [ 1 1 2 1 2 ]
[10]  [ 1 1 2 2 1 ]
[11]  [ 1 1 2 3 ]
[12]  [ 1 1 3 1 1 ]
[13]  [ 1 1 3 2 ]
[14]  [ 1 2 1 1 1 1 ]
[15]  [ 1 2 1 1 2 ]
[16]  [ 1 2 1 2 1 ]
[17]  [ 1 2 1 3 ]
[18]  [ 1 2 2 1 1 ]
[19]  [ 1 2 2 2 ]
[20]  [ 1 2 3 1 ]
[21]  [ 1 2 4 ]
[22]  [ 1 3 1 1 1 ]
[23]  [ 1 3 1 2 ]
[24]  [ 1 3 2 1 ]
[25]  [ 1 3 3 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..2000
Christian Elsholtz, Clemens Heuberger, Daniel Krenn, Algorithmic counting of nonequivalent compact Huffman codes, arXiv:1901.11343 [math.CO], 2019.
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.

Cf. A176452, A002572, A176503, A294775.

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

/* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */
N=66;  q='q+O('q^N);
t=3;  /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503  */
L=2 + 2*ceil( log(N) / log(t) );
f(k) = (1-t^k)/(1-t);
la(j) = prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) );
nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) );
dn=sum(j=0, L, (-1)^j * la(j) );
gf = nm / dn;
Vec( gf )
/* Joerg Arndt, Dec 27 2012 */

a(n) = A294775(n-1,2). - Alois P. Heinz, Nov 08 2017

Extended by Jonathan Vos Post, Aug 30 2011

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

A176431 Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of binary trees with n leaves and 2k leaves on the bottom level (n>=2, k>=1).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 2, 5, 3, 1, 9, 5, 1, 1, 16, 9, 2, 1, 28, 16, 4, 2, 50, 28, 7, 4, 89, 50, 12, 7, 1, 159, 89, 22, 12, 2, 1, 285, 159, 39, 22, 3, 2, 510, 285, 70, 39, 22, 3, 1

Offset: 2

N. J. A. Sloane, Dec 07 2010

			Triangle begins:
1
1
1 1
2 1
3 2
5 3 1
9 5 1 1
16 9 2 1
28 16 4 2
50 28 7 4
89 50 12 7 1
159 89 22 12 2 1
285 159 39 22 3 2
510 285 70 39 22 3 1

J. Paschke et al., Computing and estimating the number of n-ary Huffman sequences of a specified length, Discrete Math., 311 (2011), 1-7.

Cf. A176452, A176463. First three columns are A002572 (twice), A002573.

A176463 Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of ternary trees with 3n+1 leaves and 4k leaves on the bottom level (n>=1, k>=1).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 8, 4, 2, 1, 15, 8, 4, 2, 29, 15, 8, 4, 1, 57, 29, 15, 8, 2, 1, 112, 57, 29, 15, 4, 2, 1, 220, 112, 57, 29, 7, 4, 2

Offset: 1

N. J. A. Sloane, Dec 07 2010

			Triangle begins:
1
1
1 1
2 1 1
4 2 1 1
8 4 2 1
15 8 4 2
29 15 8 4 1
57 29 15 8 2 1
112 57 29 15 4 2 1
220 112 57 29 7 4 2

Christian Elsholtz, Clemens Heuberger and Helmut Prodinger, The number of Huffman codes, compact trees, and sums of unit fractions, IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075; also arXiv:1108.5964 [math.CO], 2011.
Jordan Paschke, Jeffrey Burkert and Rebecca Fehribach, Computing and estimating the number of n-ary Huffman sequences of a specified length, Discrete Math., 311 (2011), 1-7.

Cf. A176431, A176452, A194628 - A194633. Leading column gives A176503.

cp's OEIS Frontend

A176485 First column of triangle in A176452.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A176431 Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of binary trees with n leaves and 2k leaves on the bottom level (n>=2, k>=1).

Views

Author

Keywords

Examples

References

Crossrefs

A176463 Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of ternary trees with 3n+1 leaves and 4k leaves on the bottom level (n>=1, k>=1).

Views

Author

Keywords

Examples

Links

Crossrefs