CINXE.COM
A057864 - 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>A057864 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A057864" 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=%2fA057864">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="A057864 - 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> A057864 </div> <div class=seqname> Number of simple traceable graphs on n nodes. </div> </div> <div class=scorerefs> 21 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 2, 5, 18, 91, 734, 10030, 248427, 11482572, 1000231510</div> <div class=seqdatalinks> (<a href="/A057864/list">list</a>; <a href="/A057864/graph">graph</a>; <a href="/search?q=A057864+-id:A057864">refs</a>; <a href="/A057864/listen">listen</a>; <a href="/history?seq=A057864">history</a>; <a href="/search?q=id:A057864&fmt=text">text</a>; <a href="/A057864/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>1,3</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>Number of undirected graphs on n nodes possessing a Hamiltonian path (not circuit).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline><a href="/A057864/b057864.txt">Table of n, a(n) for n=1..11.</a></div> <div class=sectline>F. H眉ffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version f0eaa32.</div> <div class=sectline>Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TraceableGraph.html">Traceable Graph</a></div> <div class=sectline>Wikipedia, <a href="https://en.wikipedia.org/wiki/Hamiltonian_path">Hamiltonian path</a></div> <div class=sectline>Gus Wiseman, <a href="http://arxiv.org/abs/0709.0430">Enumeration of paths and cycles and e-coefficients of incomparability graphs</a>, arXiv:0709.0430 [math.CO], 2007.</div> <div class=sectline>Gus Wiseman, <a href="/A057864/a057864.png">Non-isomorphic representatives of the a(5) = 18 unlabeled simple graphs containing a Hamiltonian path</a>.</div> </div> </div> <div class=section> <div class=sectname>FORMULA</div> <div class=sectbody> <div class=sectline><a href="/A000088" title="Number of simple graphs on n unlabeled nodes.">A000088</a>(n) = a(n) + <a href="/A283420" title="Number of simple (not necessarily connected) untraceable graphs on n nodes.">A283420</a>(n). - <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Jun 17 2019</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Main diagonal of <a href="/A309524" title="Triangle read by rows: T(n,k) is the number of simple connected graphs on n nodes with longest path having k nodes, (1 <= k ...">A309524</a>.</div> <div class=sectline>The labeled case is <a href="/A326206" title="Number of n-vertex labeled simple graphs containing a Hamiltonian path.">A326206</a>.</div> <div class=sectline>The directed case is <a href="/A326221" title="Number of unlabeled n-vertex digraphs (with loops) containing a Hamiltonian path.">A326221</a> (with loops).</div> <div class=sectline>Unlabeled simple graphs not containing a Hamiltonian path are <a href="/A283420" title="Number of simple (not necessarily connected) untraceable graphs on n nodes.">A283420</a>.</div> <div class=sectline>Unlabeled simple graphs containing a Hamiltonian cycle are <a href="/A003216" title="Number of Hamiltonian graphs with n nodes.">A003216</a>.</div> <div class=sectline>Cf. <a href="/A000088" title="Number of simple graphs on n unlabeled nodes.">A000088</a>, <a href="/A006125" title="a(n) = 2^(n*(n-1)/2).">A006125</a>, <a href="/A246446" title="Number of nonhamiltonian graphs with n nodes.">A246446</a>, <a href="/A283420" title="Number of simple (not necessarily connected) untraceable graphs on n nodes.">A283420</a>, <a href="/A326205" title="Number of n-vertex labeled simple graphs not containing a Hamiltonian path.">A326205</a>, <a href="/A326217" title="Number of labeled n-vertex digraphs (without loops) containing a Hamiltonian path.">A326217</a>.</div> <div class=sectline>Sequence in context: <a href="/A227094" title="Binomial transform of A013999.">A227094</a> <a href="/A173227" title="Partial sums of A000262.">A173227</a> <a href="/A099556" title="a(n) = Sum_{k=0..2*n} (n - floor(k/2))^k.">A099556</a> * <a href="/A320154" title="Number of series-reduced balanced rooted trees whose leaves form a set partition of {1,...,n}.">A320154</a> <a href="/A032273" title="Shifts left 2 places under "DIJ" (bracelet, indistinct, labeled) transform.">A032273</a> <a href="/A143522" title="a(n) = n-fold Dumont operator of x evaluated at x=1, y=1, z=2.">A143522</a></div> <div class=sectline>Adjacent sequences: <a href="/A057861" title="floor[2^n/Fibonacci(n)].">A057861</a> <a href="/A057862" title="a(n) = 2^n mod Fibonacci(n).">A057862</a> <a href="/A057863" title="a(n) = Product_{k=1..n} (2k-1)!!.">A057863</a> * <a href="/A057865" title="Number of simple Hamilton-connected graphs on n nodes.">A057865</a> <a href="/A057866" title="Sum_{k>=1} 1/(tanh(k*Pi) * k^(4n-1)) = Pi^(4n-1)*A057866(n)/A057867(n).">A057866</a> <a href="/A057867" title="Denominator of coefficient of Pi^n in Ramanujan-like series for Zeta[4n+3].">A057867</a></div> </div> </div> <div class=section> <div class=sectname>KEYWORD</div> <div class=sectbody> <div class=sectline><span title="a sequence of nonnegative numbers">nonn</span>,<span title="more terms are needed! please extend this sequence">more</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>a(8) and a(9) from <a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a>, Jun 04 2004</div> <div class=sectline>a(10) from <a href="/wiki/User:Eric_W._Weisstein">Eric W. Weisstein</a>, May 27 2009</div> <div class=sectline>a(11) added using tinygraph by <a href="/wiki/User:Falk_H眉ffner">Falk H眉ffner</a>, Jan 19 2016</div> </div> </div> <div class=section> <div class=sectname>STATUS</div> <div class=sectbody> <div class=sectline>approved</div> </div> </div> </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 19:38 EDT 2025. Contains 382545 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>