We have a set of elements $S=\{1,2,3, . . . , N\}$ and family $F$ of $N$ triples of elements in $S$ ($N$ is a multiple of 3). Each element of $S$ appears in exactly three triples. The elements in each triple are distinct. The intersection of two triples $T\_1, T\_2$ is either empty or has exactly two elements ( $|T\_1 \cap T\_2|=2$). I guess this should be a well known combinatorial object. 



> 
> What is the number of such family of triples for each N?
> 
> 
> 


I encountered this object in constructing special instances of [exact cover problem](https://en.wikipedia.org/wiki/Exact_cover). Some of the families have exact cover. 



Counting triples family with double shared elements
I'm guessing that what matters here is subsets of size 3 from S, and that F is a special collection of such sets. It turns out that F meeting the conditions is very special, and to see this, we relax the condition on N and assume it an arbitrary large enough positive integer, instead of having three divide N.


So pick an element from S, and look at the three sets containing that element. Since they all contain this element, are distinct sets, and every two intersect in exactly two elements as they are supposed to, the union of these three sets is either four or five elements of S.


Suppose it is five elements. Then each of the three sets contain the same two elements, as two of the sets have four elements among them, the third set has the fifth element, and so the third subset shares two elements with each of the other two subsets, and must share them with the intersection. We thus have two elements in three distinct triples, and three elements in one triple each. But any other allowed triple containing one of these three outer elements has to intersect the first triples in one element exactly (otherwise we get an element in four triples). So we cannot extend the set system this way without breaking one of the conditions. Thus the union cannot contain five elements.


Thus the union of the three triples is four elements. Then the three triples cover one element three times, and the three other elements twice. Any other triple that contains two of these three elements must contain the third, otherwise again we get a triple intersecting one of the triples in one element, or else we get an element in more than three triples. The only way out is to have a fourth triple cover all these three elements.


So there is such a set system for N=4. However, for larger N, we see the above analysis carves out four elements that are involved in four triples, and no other elements are involved in those triples. To have the set system cover the other elements, we repeat the argument to carve out four more elements. In general, we repeat this construction until we exhaust N, in which case N is a multiple of 4, and if the elements are unlabelled, then there is essentially only one such F. For labelled configurations, elementary combinatorics should yield something like $(4k)!/(k!(4!)^k)$ number of systems.


Gerhard "Four Isn't A Lonely Number" Paseman, 2018.06.28.


