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

 

Logo


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

Alois P. Heinz, Table of n, a(n) for n = 0..28 (first 26 terms from Andrew Howroyd)

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.

Column k=3 of A309858.

Sequence in context: A192222 A326946 A241586 * A058882 A000659 A164919

Adjacent sequences:  A000662 A000663 A000664 * A000666 A000667 A000668

KEYWORD

nonn,nice

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 October 19 04:40 EDT 2019. Contains 328211 sequences. (Running on oeis4.)