|
|
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
|
|
|
EXAMPLE
|
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 *)
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];
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]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
|
|
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.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|