CINXE.COM
A000665 - 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>A000665 - OEIS</title> <link rel="search" type="application/opensearchdescription+xml" title="OEIS" href="/oeis.xml"> <script> var myURL = "\/A000665" 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=%2fA000665">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="A000665 - OEIS"></a> </div> <div class="motdbox"> <div class="motd"> <p>Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).</p> </div> <div class="donate"> <div id="donate-button-container"> <div id="donate-button"></div> <script src="https://www.paypalobjects.com/donate/sdk/donate-sdk.js" charset="UTF-8"></script> <script> PayPal.Donation.Button({ env:'production', hosted_button_id:'SVPGSDDCJ734A', image: { src:'https://www.paypalobjects.com/en_US/i/btn/btn_donateCC_LG.gif', alt:'Donate with PayPal button', title:'PayPal - The safer, easier way to pay online!', } }).render('#donate-button'); </script> </div> <a href="https://oeisf.org/donate/"> <strong>Other ways to Give</strong> </a> </div> </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> A000665 </div> <div class=seqname> Number of 3-uniform hypergraphs on n unlabeled nodes, or equivalently number of relations with 3 arguments on n nodes. <br><font size=-1>(Formerly M1550 N0606)</font> </div> </div> <div class=scorerefs> 22 </div> </div> <div> <div class=seqdatabox> <div class=seqdata>1, 1, 1, 2, 5, 34, 2136, 7013320, 1788782616656, 53304527811667897248, 366299663432194332594005123072, 1171638318502989084030402509596875836036608, 3517726593606526072882013063011594224625680712384971214848</div> <div class=seqdatalinks> (<a href="/A000665/list">list</a>; <a href="/A000665/graph">graph</a>; <a href="/search?q=A000665+-id:A000665">refs</a>; <a href="/A000665/listen">listen</a>; <a href="/history?seq=A000665">history</a>; <a href="/search?q=id:A000665&fmt=text">text</a>; <a href="/A000665/internal">internal format</a>) </div> </div> </div> <div class=entry> <div class=section> <div class=sectname>OFFSET</div> <div class=sectbody> <div class=sectline>0,4</div> </div> </div> <div class=section> <div class=sectname>COMMENTS</div> <div class=sectbody> <div class=sectline>The Qian reference has one incorrect term. The formula given in corollary 2.6 also contains a minor error. The second summation needs to be over p_i*p_j*p_h/lcm(p_i, p_j, p_h) rather than gcd(p_i, p_j, p_h)^2. - <a href="/wiki/User:Andrew_Howroyd">Andrew Howroyd</a>, Dec 11 2018</div> </div> </div> <div class=section> <div class=sectname>REFERENCES</div> <div class=sectbody> <div class=sectline>F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 231.</div> <div class=sectline>N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).</div> <div class=sectline>N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).</div> </div> </div> <div class=section> <div class=sectname>LINKS</div> <div class=sectbody> <div class=sectline>Alois P. Heinz, <a href="/A000665/b000665.txt">Table of n, a(n) for n = 0..28</a> (first 26 terms from Andrew Howroyd)</div> <div class=sectline>P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.</div> <div class=sectline>Victor Falgas-Ravry and Emil R. Vaughan, <a href="http://arxiv.org/abs/1110.1623">On applications of Razborov's flag algebra calculus to extremal 3-graph theory</a>, arXiv preprint arXiv:1110.1623 [math.CO], 2011.</div> <div class=sectline>W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/resolveppn/?PPN=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.</div> <div class=sectline>E. M. Palmer, <a href="http://dx.doi.org/10.1016/0012-365X(73)90069-1">On the number of n-plexes</a>, Discrete Math., 6 (1973), 377-390.</div> <div class=sectline>Jianguo Qian, <a href="https://doi.org/10.1016/j.disc.2014.03.005">Enumeration of unlabeled uniform hypergraphs</a>, Discrete Math. 326 (2014), 66--74. MR3188989.</div> </div> </div> <div class=section> <div class=sectname>EXAMPLE</div> <div class=sectbody> <div class=sectline>From <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Dec 13 2018: (Start)</div> <div class=sectline>Non-isomorphic representatives of the a(5) = 34 hypergraphs:</div> <div class=sectline> {}</div> <div class=sectline> {{123}}</div> <div class=sectline> {{125}{345}}</div> <div class=sectline> {{134}{234}}</div> <div class=sectline> {{123}{245}{345}}</div> <div class=sectline> {{124}{134}{234}}</div> <div class=sectline> {{135}{245}{345}}</div> <div class=sectline> {{145}{245}{345}}</div> <div class=sectline> {{123}{124}{134}{234}}</div> <div class=sectline> {{123}{145}{245}{345}}</div> <div class=sectline> {{124}{135}{245}{345}}</div> <div class=sectline> {{125}{135}{245}{345}}</div> <div class=sectline> {{134}{235}{245}{345}}</div> <div class=sectline> {{145}{235}{245}{345}}</div> <div class=sectline> {{123}{124}{135}{245}{345}}</div> <div class=sectline> {{123}{145}{235}{245}{345}}</div> <div class=sectline> {{124}{134}{235}{245}{345}}</div> <div class=sectline> {{134}{145}{235}{245}{345}}</div> <div class=sectline> {{135}{145}{235}{245}{345}}</div> <div class=sectline> {{145}{234}{235}{245}{345}}</div> <div class=sectline> {{123}{124}{134}{235}{245}{345}}</div> <div class=sectline> {{123}{134}{145}{235}{245}{345}}</div> <div class=sectline> {{123}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{124}{135}{145}{235}{245}{345}}</div> <div class=sectline> {{125}{135}{145}{235}{245}{345}}</div> <div class=sectline> {{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{123}{124}{135}{145}{235}{245}{345}}</div> <div class=sectline> {{124}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{125}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{134}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{123}{124}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{125}{134}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{124}{125}{134}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline> {{123}{124}{125}{134}{135}{145}{234}{235}{245}{345}}</div> <div class=sectline>(End)</div> </div> </div> <div class=section> <div class=sectname>MATHEMATICA</div> <div class=sectbody> <div class=sectline>(* about 85 seconds on a laptop computer *)</div> <div class=sectline>Needs["Combinatorica`"]; Table[A = Subsets[Range[n], {3}]; CycleIndex[Replace[Map[Sort, System`PermutationReplace[A, SymmetricGroup[n]], {2}], Table[A[[i]] -> i, {i, 1, Length[A]}], 2], s] /. Table[s[i] -> 2, {i, 1, Binomial[n, 3]}], {n, 1, 8}] (* <a href="/wiki/User:Geoffrey_Critzer">Geoffrey Critzer</a>, Oct 28 2015 *)</div> <div class=sectline>Table[Sum[2^PermutationCycles[Ordering[Map[Sort, Subsets[Range[n], {3}]/.Rule@@@Table[{i, prm[[i]]}, {i, n}], {1}]], Length], {prm, Permutations[Range[n]]}]/n!, {n, 8}] (* <a href="/wiki/User:Gus_Wiseman">Gus Wiseman</a>, Dec 13 2018 *)</div> <div class=sectline>permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];</div> <div class=sectline>edges[p_] := Sum[Ceiling[(p[[i]] - 1)*((p[[i]] - 2)/6)], {i, 1, Length[p]}] + Sum[Sum[c = p[[i]]; d = p[[j]]; GCD[c, d]*(c + d - 2 + Mod[(c - d)/GCD[c, d], 2])/2 + Sum[c*d*p[[k]]/LCM[c, d, p[[k]]], {k, 1, j - 1}], {j, 1, i - 1}], {i, 2, Length[p]}];</div> <div class=sectline>a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];</div> <div class=sectline>a /@ Range[0, 12] (* <a href="/wiki/User:Jean-François_Alcover">Jean-François Alcover</a>, Jan 08 2021, after <a href="/wiki/User:Andrew_Howroyd">Andrew Howroyd</a> *)</div> </div> </div> <div class=section> <div class=sectname>PROG</div> <div class=sectbody> <div class=sectline>(PARI)</div> <div class=sectline>permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}</div> <div class=sectline>edges(p)={sum(i=1, #p, ceil((p[i]-1)*(p[i]-2)/6)) + sum(i=2, #p, sum(j=1, i-1, my(c=p[i], d=p[j]); gcd(c, d)*(c + d - 2 + (c-d)/gcd(c, d)%2)/2 + sum(k=1, j-1, c*d*p[k]/lcm(lcm(c, d), p[k]))))}</div> <div class=sectline>a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ <a href="/wiki/User:Andrew_Howroyd">Andrew Howroyd</a>, Dec 11 2018</div> </div> </div> <div class=section> <div class=sectname>CROSSREFS</div> <div class=sectbody> <div class=sectline>Row sums of <a href="/A092337" title="Triangle read by rows: T(n,m) = number of 3-uniform hypergraphs with m hyperedges on n unlabeled nodes, where 0 <= m <= C(n,3).">A092337</a>. Spanning 3-uniform hypergraphs are counted by <a href="/A322451" title="Number of unlabeled 3-uniform hypergraphs spanning n vertices.">A322451</a>.</div> <div class=sectline>Cf. <a href="/A000088" title="Number of simple graphs on n unlabeled nodes.">A000088</a>, <a href="/A006129" title="a(0), a(1), a(2), ... satisfy Sum_{k=0..n} a(k)*binomial(n,k) = 2^binomial(n,2), for n >= 0.">A006129</a>, <a href="/A038041" title="Number of ways to partition an n-set into subsets of equal size.">A038041</a>, <a href="/A299471" title="Regular triangle where T(n,k) is the number of labeled k-uniform hypergraphs spanning n vertices.">A299471</a>, <a href="/A301922" title="Regular triangle where T(n,k) is the number of unlabeled k-uniform hypergraphs spanning n vertices.">A301922</a>, <a href="/A302374" title="Number of families of 3-subsets of an n-set that cover every element.">A302374</a>, <a href="/A302394" title="Number of families of 3-subsets of an n-set that cover all 2-subsets.">A302394</a>, <a href="/A306017" title="Number of non-isomorphic multiset partitions of weight n in which all parts have the same size.">A306017</a>, <a href="/A306021" title="Number of set-systems spanning {1,...,n} in which all sets have the same size.">A306021</a>, <a href="/A320395" title="Number of non-isomorphic 3-uniform multiset systems over {1,...,n}.">A320395</a>.</div> <div class=sectline>Column k=3 of <a href="/A309858" title="Number A(n,k) of k-uniform hypergraphs on n unlabeled nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.">A309858</a>.</div> <div class=sectline>Sequence in context: <a href="/A192222" title="a(n) = Fibonacci(2^n + 1).">A192222</a> <a href="/A326946" title="Number of unlabeled T_0 set-systems on n vertices.">A326946</a> <a href="/A241586" title="Erroneous version of A000665.">A241586</a> * <a href="/A058882" title="Erroneous version of A000665.">A058882</a> <a href="/A000659" title="a(n) = 2^a(n-1) + a(n-2).">A000659</a> <a href="/A164919" title="Number of simple connected cubic nonhamiltonian graphs on 2n nodes.">A164919</a></div> <div class=sectline>Adjacent sequences: <a href="/A000662" title="Number of relations with 3 arguments on n nodes.">A000662</a> <a href="/A000663" title="Number of relations on an infinite set.">A000663</a> <a href="/A000664" title="Number of graphs with n edges.">A000664</a> * <a href="/A000666" title="Number of symmetric relations on n nodes.">A000666</a> <a href="/A000667" title="Boustrophedon transform of all-1's sequence.">A000667</a> <a href="/A000668" title="Mersenne primes (primes of the form 2^n - 1).">A000668</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="an exceptionally nice sequence">nice</span></div> </div> </div> <div class=section> <div class=sectname>AUTHOR</div> <div class=sectbody> <div class=sectline><a href="/wiki/User:N._J._A._Sloane">N. J. A. Sloane</a></div> </div> </div> <div class=section> <div class=sectname>EXTENSIONS</div> <div class=sectbody> <div class=sectline>Corrected and extended by <a href="/wiki/User:Vladeta_Jovovic">Vladeta Jovovic</a></div> <div class=sectline>a(0)=1 prepended and a(12) from <a href="/wiki/User:Andrew_Howroyd">Andrew Howroyd</a>, Dec 11 2018</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 December 11 02:47 EST 2024. Contains 378602 sequences.</div> <div class=legal> <a href="/wiki/Legal_Documents">License Agreements, Terms of Use, Privacy Policy</a> </div> </div> </center> </div> </body> </html>