login
Leading column of triangle in A176463.
11

%I #30 Mar 21 2019 17:18:13

%S 1,1,1,2,4,8,15,29,57,112,220,432,848,1666,3273,6430,12632,24816,

%T 48754,95783,188177,369696,726312,1426930,2803381,5507590,10820345,

%U 21257915,41763825,82050242,161197933,316693445,622183778,1222357651,2401474098,4717995460

%N Leading column of triangle in A176463.

%C a(n+1) is the number of compositions n=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 4*p(k+1), see example. [_Joerg Arndt_, Dec 18 2012]

%H Alois P. Heinz, <a href="/A176503/b176503.txt">Table of n, a(n) for n = 1..1000</a>

%H Christian Elsholtz, Clemens Heuberger, Daniel Krenn, <a href="https://arxiv.org/abs/1901.11343">Algorithmic counting of nonequivalent compact Huffman codes</a>, arXiv:1901.11343 [math.CO], 2019.

%H Christian Elsholtz, Clemens Heuberger, Helmut Prodinger, <a href="http://arxiv.org/abs/1108.5964">The number of Huffman codes, compact trees, and sums of unit fractions</a>, arXiv:1108.5964v1 [math.CO], Aug 30, 2011. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.

%F a(n) = A294775(n-1,3). - _Alois P. Heinz_, Nov 08 2017

%e From _Joerg Arndt_, Dec 18 2012: (Start)

%e There are a(6+1)=15 compositions 6=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 4*p(k+1):

%e [ 1] [ 1 1 1 1 1 1 ]

%e [ 2] [ 1 1 1 1 2 ]

%e [ 3] [ 1 1 1 2 1 ]

%e [ 4] [ 1 1 1 3 ]

%e [ 5] [ 1 1 2 1 1 ]

%e [ 6] [ 1 1 2 2 ]

%e [ 7] [ 1 1 3 1 ]

%e [ 8] [ 1 1 4 ]

%e [ 9] [ 1 2 1 1 1 ]

%e [10] [ 1 2 1 2 ]

%e [11] [ 1 2 2 1 ]

%e [12] [ 1 2 3 ]

%e [13] [ 1 3 1 1 ]

%e [14] [ 1 3 2 ]

%e [15] [ 1 4 1 ]

%e (End)

%t 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]}]]];

%t a[n_] := b[3n-2, 1, 4];

%t Array[a, 40] (* _Jean-François Alcover_, Jul 21 2018, after _Alois P. Heinz_ *)

%o (PARI)

%o /* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */

%o N=66; q='q+O('q^N);

%o t=4; /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503 */

%o L=2 + 2*ceil( log(N) / log(t) );

%o f(k) = (1-t^k)/(1-t);

%o la(j) = prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) );

%o nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) );

%o dn=sum(j=0, L, (-1)^j * la(j) );

%o gf = nm / dn;

%o Vec( gf )

%o /* _Joerg Arndt_, Dec 27 2012 */

%Y Cf. A176463, A194628 - A194633, A294775.

%K nonn

%O 1,4

%A _N. J. A. Sloane_, Dec 07 2010

%E Added terms beyond a(13)=848, _Joerg Arndt_, Dec 18 2012