Unique numbers in two sets of three

Cook_Me_Plox · Aug 17, 2012

Hi, sorry if this is in the wrong section. Some of the stuff in this section is way over my head anyway.

I have 10 sets of 3 numbers ranging from 1 to 10. They are interesting in that each number appears three time, no number appears twice in the same set, and no two numbers appear together in different sets more than once.

{1,2,7}
{1,8,0}
{1,5,6}
{3,7,0}
{5,7,9}
{4,5,0}
{2,3,8}
{2,6,9}
{4,6,8}
{3,4,9}

If you took any combination of two of the sets, how many "unique" numbers would you have? In this case a unique number is just one that appears in the sets, so the first two {1,2,7} and {1,8,0} would have unique numbers {1,2,7,8,0}. As it turns out, of the 45 possible combinations of two sets, 30 contain 5 uniques, and 15 contain 6 uniques. I know this because I simulated it.

My question is, is there any way to tell the number times a certain amount of unique numbers will show up in the set without calculating each combination? 30 and 15 are so...symmetric to 45 that I have to imagine there's some easier way to do this. I know that doing this for combinations of 2 sets of three numbers from 1-10 looks easy (and it is), but I'm hoping that by looking at this, there's a more general formula for which you can determine the amount of uniques with combinations of p sets of q parts up to r. For instance, how many different combinations of 50 sets of 5 numbers ranging from 1-1000 will have exactly 200 unique numbers?

I hope someone can either help me out or point me in the right direction. Many thanks.

micromass · Aug 17, 2012

It is not hard to see in this case.

Take an arbitrary set. Let's find the number of sets disjoint with that set.
Let's say our set is {x,y,z}. There are two other sets containing x, these sets are not disjoint with {x,y,z}. Likewise, there are two other sets containing y. And there are two other sets containing z. These sets cannot all be disjoint. So, in particular, there are 7 sets (including {x,y,z}) not disjoint with {x,y,z}. So there are 10-7=3 sets disjoint with {x,y,z}.

From 3 sets, it is possible to pick two sets in 3 different ways. Now, we can do that for every set. There are 10 different sets in total, and 3 sets disjoint with every set. So in total, there are 30 different combinations of disjoint sets.
However, we counted double now. Indeed, if we pick a set {x,y,z} and see that {a,b,c} is disjoint, then this is the same as picking the set {a,b,c} and seeing that {x,y,z} is disjoint. So we counted {x,y,z} and {a,b,c} two times. So we must divide 30 by 2. This gives us 15 combinations of disjoint sets.

haruspex · Aug 17, 2012

If there are (essentially) different families of 10 sets 3 satisfying the same conditions, they could have different counts of cardinalities of pairwise unions. So it seems unlikely that a formula can be provided. Or are you claiming that the conditions uniquely determine the family (up to isomorphism)?

Cook_Me_Plox · Aug 18, 2012

micromass said: ↑

It is not hard to see in this case.

Take an arbitrary set. Let's find the number of sets disjoint with that set.
Let's say our set is {x,y,z}. There are two other sets containing x, these sets are not disjoint with {x,y,z}. Likewise, there are two other sets containing y. And there are two other sets containing z. These sets cannot all be disjoint. So, in particular, there are 7 sets (including {x,y,z}) not disjoint with {x,y,z}. So there are 10-7=3 sets disjoint with {x,y,z}.

From 3 sets, it is possible to pick two sets in 3 different ways. Now, we can do that for every set. There are 10 different sets in total, and 3 sets disjoint with every set. So in total, there are 30 different combinations of disjoint sets.
However, we counted double now. Indeed, if we pick a set {x,y,z} and see that {a,b,c} is disjoint, then this is the same as picking the set {a,b,c} and seeing that {x,y,z} is disjoint. So we counted {x,y,z} and {a,b,c} two times. So we must divide 30 by 2. This gives us 15 combinations of disjoint sets.

Thank you, that's what I was looking for. I also want to find out if there's a computationally easy way to generalize this for combinations of three or more.

haruspex said: ↑

If there are (essentially) different families of 10 sets 3 satisfying the same conditions, they could have different counts of cardinalities of pairwise unions. So it seems unlikely that a formula can be provided. Or are you claiming that the conditions uniquely determine the family (up to isomorphism)?

The sets were determined by labeling the edges of a 5-vertice complete graph from 1-10 and writing down each set of edges that created a triangle. The actual parts of the set would have differed had I labelled them differently, but they would still essentially be the same.

haruspex · Aug 18, 2012

Cook_Me_Plox said: ↑

The sets were determined by labeling the edges of a 5-vertice complete graph from 1-10 and writing down each set of edges that created a triangle.

OK, so the underlying question was in how many ways can you choose two triangles from K₅ with no edges in common. That model makes it easier. The following is the same as micromass' logic, but expressed in terms of the K₅:
Pick any of the 10 triangles. For the second triangle, you can reuse at most one vertex; but there are only two you haven't used, so you must reuse exactly one. There are three choices for that. Could have picked the two triangles in the other order, 10 * 3 /2 = 15.

Cook_Me_Plox · Aug 18, 2012

haruspex said: ↑

OK, so the underlying question was in how many ways can you choose two triangles from K₅ with no edges in common. That model makes it easier. The following is the same as micromass' logic, but expressed in terms of the K₅:
Pick any of the 10 triangles. For the second triangle, you can reuse at most one vertex; but there are only two you haven't used, so you must reuse exactly one. There are three choices for that. Could have picked the two triangles in the other order, 10 * 3 /2 = 15.

How can I figure that out for three triangles or more? Or for K₆ and above? Or for something more complicated than triangles?

haruspex · Aug 18, 2012

Cook_Me_Plox said: ↑

How can I figure that out for three triangles or more?

You cannot pick a third triangle edge-disjoint from the first two. Is that what you meant?

Or for K₆ and above?

Let's start with asking what is the max number of disjoint triangles that can be found from K_n. For K₇, it's 7, and I believe the structure is that of the Fano plane. This suggests to me that a totally general formula is going to be tough.
Dropping back to choosing just two triangles from K_n:
Pick any of the ⁿC₃ triangles; there are 3 * ^n-3C₂ ways in which the second triangle shares a vertex with the first, and ^n-3C₃ in which it does not. Summing and halving, I get ⁿC₅(n+4)5/3.