login
Number of 3-uniform hypergraphs spanning n labeled vertices where every two edges have exactly one vertex in common.
4

%I #17 Feb 12 2022 20:29:03

%S 1,0,0,1,0,15,150,1815,0,945,0,10395,0,135135,0,2027025,0,34459425,0,

%T 654729075,0,13749310575,0,316234143225,0,7905853580625,0,

%U 213458046676875,0,6190283353629375,0,191898783962510625,0,6332659870762850625,0,221643095476699771875

%N Number of 3-uniform hypergraphs spanning n labeled vertices where every two edges have exactly one vertex in common.

%C The only way to cover more than 7 vertices is with edges all having a single common vertex. For the special cases of n = 6 or n = 7, there are also covers without a common vertex. - _Andrew Howroyd_, Aug 15 2019

%H Andrew Howroyd, <a href="/A323298/b323298.txt">Table of n, a(n) for n = 0..200</a>

%F a(2*n) = 0 for n > 3; a(2*n-1) = A001147(n) for n > 4. - _Andrew Howroyd_, Aug 15 2019

%e The a(5) = 15 hypergraphs:

%e {{1,4,5},{2,3,5}}

%e {{1,4,5},{2,3,4}}

%e {{1,3,5},{2,4,5}}

%e {{1,3,5},{2,3,4}}

%e {{1,3,4},{2,4,5}}

%e {{1,3,4},{2,3,5}}

%e {{1,2,5},{3,4,5}}

%e {{1,2,5},{2,3,4}}

%e {{1,2,5},{1,3,4}}

%e {{1,2,4},{3,4,5}}

%e {{1,2,4},{2,3,5}}

%e {{1,2,4},{1,3,5}}

%e {{1,2,3},{3,4,5}}

%e {{1,2,3},{2,4,5}}

%e {{1,2,3},{1,4,5}}

%e The following are non-isomorphic representatives of the 5 unlabeled 3-uniform hypergraphs spanning 7 vertices in which every two edges have exactly one vertex in common, and their multiplicities in the labeled case, which add up to a(7) = 1815.

%e 105 X {{1,2,7},{3,4,7},{5,6,7}}

%e 840 X {{1,4,5},{2,4,6},{3,4,7},{5,6,7}}

%e 630 X {{1,4,5},{2,3,5},{2,4,6},{3,4,7},{5,6,7}}

%e 210 X {{1,3,6},{1,4,5},{2,3,5},{2,4,6},{3,4,7},{5,6,7}}

%e 30 X {{1,2,7},{1,3,6},{1,4,5},{2,3,5},{2,4,6},{3,4,7},{5,6,7}}

%e From _Andrew Howroyd_, Aug 15 2019: (Start)

%e The following are non-isomorphic representatives of the 2 unlabeled 3-uniform hypergraphs spanning 6 vertices in which every two edges have exactly one vertex in common, and their multiplicities in the labeled case, which add up to a(6) = 150.

%e 120 X {{1,2,3},{1,4,5},{3,5,6}}

%e 30 X {{1,2,3},{1,4,5},{3,5,6},{2,4,6}}

%e (End)

%t stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];

%t Table[Length[Select[stableSets[Subsets[Range[n],{3}],Length[Intersection[#1,#2]]!=1&],Union@@#==Range[n]&]],{n,10}]

%o (PARI) a(n)={if(n%2, if(n<=3, n==3, if(n==7, 1815, n!/(2^(n\2)*(n\2)!))), if(n==6, 150, n==0))} \\ _Andrew Howroyd_, Aug 15 2019

%Y Cf. A001147, A025035, A125791, A190865, A289837, A299471, A302374, A302394, A322451, A323293, A323296, A323297, A323299.

%K nonn

%O 0,6

%A _Gus Wiseman_, Jan 11 2019

%E Terms a(13) and beyond from _Andrew Howroyd_, Aug 15 2019