login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000665 Number of 3-uniform hypergraphs on n unlabeled nodes, or equivalently number of relations with 3 arguments on n nodes.
(Formerly M1550 N0606)
13
1, 1, 1, 2, 5, 34, 2136, 7013320, 1788782616656, 53304527811667897248, 366299663432194332594005123072, 1171638318502989084030402509596875836036608, 3517726593606526072882013063011594224625680712384971214848 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

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

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 231.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..25

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Victor Falgas-Ravry and Emil R. Vaughan, On applications of Razborov's flag algebra calculus to extremal 3-graph theory, arXiv preprint arXiv:1110.1623 [math.CO], 2011.

W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.

E. M. Palmer, On the number of n-plexes, Discrete Math., 6 (1973), 377-390.

Jianguo Qian, Enumeration of unlabeled uniform hypergraphs, Discrete Math. 326 (2014), 66--74. MR3188989.

EXAMPLE

From Gus Wiseman, Dec 13 2018: (Start)

Non-isomorphic representatives of the a(5) = 34 hypergraphs:

  {}

  {{123}}

  {{125}{345}}

  {{134}{234}}

  {{123}{245}{345}}

  {{124}{134}{234}}

  {{135}{245}{345}}

  {{145}{245}{345}}

  {{123}{124}{134}{234}}

  {{123}{145}{245}{345}}

  {{124}{135}{245}{345}}

  {{125}{135}{245}{345}}

  {{134}{235}{245}{345}}

  {{145}{235}{245}{345}}

  {{123}{124}{135}{245}{345}}

  {{123}{145}{235}{245}{345}}

  {{124}{134}{235}{245}{345}}

  {{134}{145}{235}{245}{345}}

  {{135}{145}{235}{245}{345}}

  {{145}{234}{235}{245}{345}}

  {{123}{124}{134}{235}{245}{345}}

  {{123}{134}{145}{235}{245}{345}}

  {{123}{145}{234}{235}{245}{345}}

  {{124}{135}{145}{235}{245}{345}}

  {{125}{135}{145}{235}{245}{345}}

  {{135}{145}{234}{235}{245}{345}}

  {{123}{124}{135}{145}{235}{245}{345}}

  {{124}{135}{145}{234}{235}{245}{345}}

  {{125}{135}{145}{234}{235}{245}{345}}

  {{134}{135}{145}{234}{235}{245}{345}}

  {{123}{124}{135}{145}{234}{235}{245}{345}}

  {{125}{134}{135}{145}{234}{235}{245}{345}}

  {{124}{125}{134}{135}{145}{234}{235}{245}{345}}

  {{123}{124}{125}{134}{135}{145}{234}{235}{245}{345}}

(End)

MATHEMATICA

(* about 85 seconds on a laptop computer *)

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 *)

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 *)

PROG

(PARI)

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}

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]))))}

a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Dec 11 2018

CROSSREFS

Row sums of A092337. Spanning 3-uniform hypergraphs are counted by A322451.

Cf. A000088, A006129, A038041, A299471, A301922, A302374, A302394, A306017, A306021, A320395.

Sequence in context: A002665 A192222 A241586 * A058882 A000659 A164919

Adjacent sequences:  A000662 A000663 A000664 * A000666 A000667 A000668

KEYWORD

nonn,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

Corrected and extended by Vladeta Jovovic

a(0)=1 prepended and a(12) from Andrew Howroyd, Dec 11 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 18 05:48 EST 2018. Contains 318215 sequences. (Running on oeis4.)