CINXE.COM
A176503 - OEIS
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> <html> <head> <link rel="stylesheet" href="/styles.css"> <meta name="format-detection" content="telephone=no"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta name=viewport content="width=device-width, initial-scale=1"> <meta name="keywords" content="OEIS,integer sequences,Sloane" /> <title>A176503 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A176503\/internal" function redir() { var host = document.location.hostname; if(host != "oeis.org" && host != "127.0.0.1" && !/^([0-9.]+)$/.test(host) && host != "localhost" && host != "localhost.localdomain") { document.location = "https"+":"+"//"+"oeis"+".org/" + myURL; } } function sf() { if(document.location.pathname == "/" && document.f) document.f.q.focus(); } </script> </head> <body bgcolor=#ffffff onload="redir();sf()"> <div class=loginbar> <div class=login> <a href="/login?redirect=%2fA176503%2finternal">login</a> </div> </div> <div class=center><div class=top> <center> <div class=donors> The OEIS is supported by <a href="http://oeisf.org/#DONATE">the many generous donors to the OEIS Foundation</a>. </div> <div class=banner> <a href="/"><img class=banner border="0" width="600" src="/banner2021.jpg" alt="A176503 - OEIS"></a> </div> </center> </div></div> <div class=center><div class=pagebody> <div class=searchbarcenter> <form name=f action="/search" method="GET"> <div class=searchbargreet> <div class=searchbar> <div class=searchq> <input class=searchbox maxLength=1024 name=q value="" title="Search Query"> </div> <div class=searchsubmit> <input type=submit value="Search" name=go> </div> <div class=hints> <span class=hints><a href="/hints.html">Hints</a></span> </div> </div> <div class=searchgreet> (Greetings from <a href="/welcome">The On-Line Encyclopedia of Integer Sequences</a>!) </div> </div> </form> </div> <div class=sequence> <div class=space1></div> <div class=line></div> <div class=seqhead> <div class=seqnumname> <div class=seqnum> <a href="/A176503">A176503</a> </div> <div class=seqname> Leading column of triangle in <a href="/A176463" title="Irregular triangle read by rows: T(n,k) = number of Huffman-equivalence classes of ternary trees with 3n+1 leaves and 4k lea...">A176463</a>. </div> </div> <div class=scorerefs> 11 </div> </div> <div> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%I #30 Mar 21 2019 17:18:13 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%S 1,1,1,2,4,8,15,29,57,112,220,432,848,1666,3273,6430,12632,24816, </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%T 48754,95783,188177,369696,726312,1426930,2803381,5507590,10820345, </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%U 21257915,41763825,82050242,161197933,316693445,622183778,1222357651,2401474098,4717995460 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%N Leading column of triangle in A176463. </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%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] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%H Alois P. Heinz, <a href="/A176503/b176503.txt">Table of n, a(n) for n = 1..1000</a> </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%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. </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%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. </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%F a(n) = A294775(n-1,3). - _Alois P. Heinz_, Nov 08 2017 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e From _Joerg Arndt_, Dec 18 2012: (Start) </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%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): </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 1] [ 1 1 1 1 1 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 2] [ 1 1 1 1 2 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 3] [ 1 1 1 2 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 4] [ 1 1 1 3 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 5] [ 1 1 2 1 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 6] [ 1 1 2 2 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 7] [ 1 1 3 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 8] [ 1 1 4 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [ 9] [ 1 2 1 1 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [10] [ 1 2 1 2 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [11] [ 1 2 2 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [12] [ 1 2 3 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [13] [ 1 3 1 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [14] [ 1 3 2 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e [15] [ 1 4 1 ] </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%e (End) </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%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]}]]]; </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%t a[n_] := b[3n-2, 1, 4]; </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%t Array[a, 40] (* _Jean-Fran莽ois Alcover_, Jul 21 2018, after _Alois P. Heinz_ *) </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o (PARI) </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o /* g.f. as given in the Elsholtz/Heuberger/Prodinger reference */ </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o N=66; q='q+O('q^N); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o t=4; /* t-ary: t=2 for A002572, t=3 for A176485, t=4 for A176503 */ </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o L=2 + 2*ceil( log(N) / log(t) ); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o f(k) = (1-t^k)/(1-t); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o la(j) = prod(i=1, j, q^f(i) / ( 1 - q^f(i) ) ); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o nm=sum(j=0, L, (-1)^j * q^f(j) * la(j) ); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o dn=sum(j=0, L, (-1)^j * la(j) ); </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o gf = nm / dn; </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o Vec( gf ) </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%o /* _Joerg Arndt_, Dec 27 2012 */ </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%Y Cf. A176463, A194628 - A194633, A294775. </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%K nonn </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%O 1,4 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%A _N. J. A. Sloane_, Dec 07 2010 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt>%E Added terms beyond a(13)=848, _Joerg Arndt_, Dec 18 2012 </tt></p> <p style="text-indent: -2em; margin-left: 2em; margin-top: 0; margin-bottom: 0;"><tt></tt></p> </div> <div class=space10></div> </div> </div></div> <p> <div class=footerpad></div> <div class=footer> <center> <div class=bottom> <div class=linksbar> <a href="/">Lookup</a> <a href="/wiki/Welcome"><font color="red">Welcome</font></a> <a href="/wiki/Main_Page"><font color="red">Wiki</font></a> <a href="/wiki/Special:RequestAccount">Register</a> <a href="/play.html">Music</a> <a href="/plot2.html">Plot 2</a> <a href="/demo1.html">Demos</a> <a href="/wiki/Index_to_OEIS">Index</a> <a href="/webcam">WebCam</a> <a href="/Submit.html">Contribute</a> <a href="/eishelp2.html">Format</a> <a href="/wiki/Style_Sheet">Style Sheet</a> <a href="/transforms.html">Transforms</a> <a href="/ol.html">Superseeker</a> <a href="/recent">Recents</a> </div> <div class=linksbar> <a href="/community.html">The OEIS Community</a> </div> <div class=linksbar> Maintained by <a href="http://oeisf.org">The OEIS Foundation Inc.</a> </div> <div class=dbinfo>Last modified April 6 23:12 EDT 2025. Contains 382550 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>