cp's OEIS Frontend

A000665 Number of 3-uniform hypergraphs on n unlabeled nodes, or equivalently number of relations with 3 arguments on n nodes.

%I A000665 M1550 N0606 #62 Jan 08 2021 04:18:59
%S A000665 1,1,1,2,5,34,2136,7013320,1788782616656,53304527811667897248,
%T A000665 366299663432194332594005123072,
%U A000665 1171638318502989084030402509596875836036608,3517726593606526072882013063011594224625680712384971214848
%N A000665 Number of 3-uniform hypergraphs on n unlabeled nodes, or equivalently number of relations with 3 arguments on n nodes.
%C A000665 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. - _Andrew Howroyd_, Dec 11 2018
%D A000665 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 231.
%D A000665 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000665 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000665 Alois P. Heinz, <a href="/A000665/b000665.txt">Table of n, a(n) for n = 0..28</a> (first 26 terms from Andrew Howroyd)
%H A000665 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.
%H A000665 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.
%H A000665 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.
%H A000665 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.
%H A000665 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.
%e A000665 From _Gus Wiseman_, Dec 13 2018: (Start)
%e A000665 Non-isomorphic representatives of the a(5) = 34 hypergraphs:
%e A000665   {}
%e A000665   {{123}}
%e A000665   {{125}{345}}
%e A000665   {{134}{234}}
%e A000665   {{123}{245}{345}}
%e A000665   {{124}{134}{234}}
%e A000665   {{135}{245}{345}}
%e A000665   {{145}{245}{345}}
%e A000665   {{123}{124}{134}{234}}
%e A000665   {{123}{145}{245}{345}}
%e A000665   {{124}{135}{245}{345}}
%e A000665   {{125}{135}{245}{345}}
%e A000665   {{134}{235}{245}{345}}
%e A000665   {{145}{235}{245}{345}}
%e A000665   {{123}{124}{135}{245}{345}}
%e A000665   {{123}{145}{235}{245}{345}}
%e A000665   {{124}{134}{235}{245}{345}}
%e A000665   {{134}{145}{235}{245}{345}}
%e A000665   {{135}{145}{235}{245}{345}}
%e A000665   {{145}{234}{235}{245}{345}}
%e A000665   {{123}{124}{134}{235}{245}{345}}
%e A000665   {{123}{134}{145}{235}{245}{345}}
%e A000665   {{123}{145}{234}{235}{245}{345}}
%e A000665   {{124}{135}{145}{235}{245}{345}}
%e A000665   {{125}{135}{145}{235}{245}{345}}
%e A000665   {{135}{145}{234}{235}{245}{345}}
%e A000665   {{123}{124}{135}{145}{235}{245}{345}}
%e A000665   {{124}{135}{145}{234}{235}{245}{345}}
%e A000665   {{125}{135}{145}{234}{235}{245}{345}}
%e A000665   {{134}{135}{145}{234}{235}{245}{345}}
%e A000665   {{123}{124}{135}{145}{234}{235}{245}{345}}
%e A000665   {{125}{134}{135}{145}{234}{235}{245}{345}}
%e A000665   {{124}{125}{134}{135}{145}{234}{235}{245}{345}}
%e A000665   {{123}{124}{125}{134}{135}{145}{234}{235}{245}{345}}
%e A000665 (End)
%t A000665 (* about 85 seconds on a laptop computer *)
%t A000665 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}] (* _Geoffrey Critzer_, Oct 28 2015 *)
%t A000665 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}] (* _Gus Wiseman_, Dec 13 2018 *)
%t A000665 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];
%t A000665 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]}];
%t A000665 a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t A000665 a /@ Range[0, 12] (* _Jean-François Alcover_, Jan 08 2021, after _Andrew Howroyd_ *)
%o A000665 (PARI)
%o A000665 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}
%o A000665 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]))))}
%o A000665 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Dec 11 2018
%Y A000665 Row sums of A092337. Spanning 3-uniform hypergraphs are counted by A322451.
%Y A000665 Cf. A000088, A006129, A038041, A299471, A301922, A302374, A302394, A306017, A306021, A320395.
%Y A000665 Column k=3 of A309858.
%K A000665 nonn,nice
%O A000665 0,4
%A A000665 _N. J. A. Sloane_
%E A000665 Corrected and extended by _Vladeta Jovovic_
%E A000665 a(0)=1 prepended and a(12) from _Andrew Howroyd_, Dec 11 2018