cp's OEIS Frontend

A176485 First column of triangle in A176452.

%I A176485 #41 Mar 21 2019 18:01:29
%S A176485 1,1,1,2,4,7,13,25,48,92,176,338,649,1246,2392,4594,8823,16945,32545,
%T A176485 62509,120060,230598,442910,850701,1633948,3138339,6027842,11577747,
%U A176485 22237515,42711863,82037200,157569867,302646401,581296715,1116503866,2144482948,4118935248,7911290530
%N A176485 First column of triangle in A176452.
%C A176485 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]
%C A176485 Row 2 of Table 1 of Elsholtz, row 1 being A002572. - _Jonathan Vos Post_, Aug 30 2011
%H A176485 Alois P. Heinz, <a href="/A176485/b176485.txt">Table of n, a(n) for n = 1..2000</a>
%H A176485 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 A176485 Christian Elsholtz, Clemens Heuberger, Helmut Prodinger, <a href="https://arxiv.org/abs/1108.5964">The number of Huffman codes, compact trees, and sums of unit fractions</a>, arXiv:1108.5964 [math.CO], Aug 30, 2011. Also IEEE Trans. Information Theory, Vol. 59, No. 2, 2013 pp. 1065-1075.
%F A176485 a(n) = A294775(n-1,2). - _Alois P. Heinz_, Nov 08 2017
%e A176485 From _Joerg Arndt_, Dec 18 2012: (Start)
%e A176485 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):
%e A176485 [ 1]  [ 1 1 1 1 1 1 1 ]
%e A176485 [ 2]  [ 1 1 1 1 1 2 ]
%e A176485 [ 3]  [ 1 1 1 1 2 1 ]
%e A176485 [ 4]  [ 1 1 1 1 3 ]
%e A176485 [ 5]  [ 1 1 1 2 1 1 ]
%e A176485 [ 6]  [ 1 1 1 2 2 ]
%e A176485 [ 7]  [ 1 1 1 3 1 ]
%e A176485 [ 8]  [ 1 1 2 1 1 1 ]
%e A176485 [ 9]  [ 1 1 2 1 2 ]
%e A176485 [10]  [ 1 1 2 2 1 ]
%e A176485 [11]  [ 1 1 2 3 ]
%e A176485 [12]  [ 1 1 3 1 1 ]
%e A176485 [13]  [ 1 1 3 2 ]
%e A176485 [14]  [ 1 2 1 1 1 1 ]
%e A176485 [15]  [ 1 2 1 1 2 ]
%e A176485 [16]  [ 1 2 1 2 1 ]
%e A176485 [17]  [ 1 2 1 3 ]
%e A176485 [18]  [ 1 2 2 1 1 ]
%e A176485 [19]  [ 1 2 2 2 ]
%e A176485 [20]  [ 1 2 3 1 ]
%e A176485 [21]  [ 1 2 4 ]
%e A176485 [22]  [ 1 3 1 1 1 ]
%e A176485 [23]  [ 1 3 1 2 ]
%e A176485 [24]  [ 1 3 2 1 ]
%e A176485 [25]  [ 1 3 3 ]
%e A176485 (End)
%t A176485 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 A176485 a[n_] := b[2n-1, 1, 3];
%t A176485 Array[a, 40] (* _Jean-François Alcover_, Jul 21 2018, after _Alois P. Heinz_ *)
%o A176485 (PARI)
%o A176485 /* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */
%o A176485 N=66;  q='q+O('q^N);
%o A176485 t=3;  /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503  */
%o A176485 L=2 + 2*ceil( log(N) / log(t) );
%o A176485 f(k) = (1-t^k)/(1-t);
%o A176485 la(j) = prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) );
%o A176485 nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) );
%o A176485 dn=sum(j=0, L, (-1)^j * la(j) );
%o A176485 gf = nm / dn;
%o A176485 Vec( gf )
%o A176485 /* _Joerg Arndt_, Dec 27 2012 */
%Y A176485 Cf. A176452, A002572, A176503, A294775.
%K A176485 nonn
%O A176485 1,4
%A A176485 _N. J. A. Sloane_, Dec 07 2010
%E A176485 Extended by _Jonathan Vos Post_, Aug 30 2011
%E A176485 Added terms beyond a(20)=62509, _Joerg Arndt_, Dec 18 2012.