cp's OEIS Frontend

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

%I A194628 #35 Feb 15 2020 23:54:54
%S A194628 1,1,1,2,4,8,16,31,61,121,240,476,944,1872,3712,7362,14601,28958,
%T A194628 57432,113904,225904,448034,888583,1762321,3495200,6932008,13748208,
%U A194628 27266738,54077957,107252486,212713209,421872826,836697836,1659417786,3291113315,6527245245,12945446241,25674625681
%N A194628 Arises in enumerating Huffman codes, compact trees, and sums of unit fractions.
%C A194628 a(n+1) is the number of compositions n=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 5*p(k+1), see example. - _Joerg Arndt_, Dec 18 2012
%C A194628 Row 4 of Table 1 of Elsholtz, row 1 being A002572, row 2 being A176485, and row 3 being A176503.
%H A194628 Alois P. Heinz, <a href="/A194628/b194628.txt">Table of n, a(n) for n = 1..1000</a>
%H A194628 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.
%F A194628 a(n) = A294775(n-1,4). - _Alois P. Heinz_, Nov 08 2017
%e A194628 From _Joerg Arndt_, Dec 18 2012: (Start)
%e A194628 There are a(6+1)=16 compositions 6=p(1)+p(2)+...+p(m) with p(1)=1 and p(k) <= 5*p(k+1):
%e A194628 [ 1]  [ 1 1 1 1 1 1 ]
%e A194628 [ 2]  [ 1 1 1 1 2 ]
%e A194628 [ 3]  [ 1 1 1 2 1 ]
%e A194628 [ 4]  [ 1 1 1 3 ]
%e A194628 [ 5]  [ 1 1 2 1 1 ]
%e A194628 [ 6]  [ 1 1 2 2 ]
%e A194628 [ 7]  [ 1 1 3 1 ]
%e A194628 [ 8]  [ 1 1 4 ]
%e A194628 [ 9]  [ 1 2 1 1 1 ]
%e A194628 [10]  [ 1 2 1 2 ]
%e A194628 [11]  [ 1 2 2 1 ]
%e A194628 [12]  [ 1 2 3 ]
%e A194628 [13]  [ 1 3 1 1 ]
%e A194628 [14]  [ 1 3 2 ]
%e A194628 [15]  [ 1 4 1 ]
%e A194628 [16]  [ 1 5 ]
%e A194628 (End)
%t A194628 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 A194628 a[n_] := b[4n - 3, 1, 5];
%t A194628 Array[a, 40] (* _Jean-François Alcover_, Jul 21 2018, after _Alois P. Heinz_ *)
%o A194628 (PARI) /* see A002572, set t=5 */
%Y A194628 Cf. A002572, A176485, A176503, A294775.
%K A194628 nonn
%O A194628 1,4
%A A194628 _Jonathan Vos Post_, Aug 30 2011
%E A194628 Terms beyond a(20)=113904 added by _Joerg Arndt_, Dec 18 2012
%E A194628 Invalid empirical g.f. removed by _Alois P. Heinz_, Nov 08 2017