Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Unique numbers in two sets of three

  1. Aug 17, 2012 #1
    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.


    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.
    Last edited: Aug 17, 2012
  2. jcsd
  3. Aug 17, 2012 #2
    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.
  4. Aug 17, 2012 #3


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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)?
  5. Aug 18, 2012 #4
    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.

    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.
    Last edited: Aug 18, 2012
  6. Aug 18, 2012 #5


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, so the underlying question was in how many ways can you choose two triangles from K5 with no edges in common. That model makes it easier. The following is the same as micromass' logic, but expressed in terms of the K5:
    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.
  7. Aug 18, 2012 #6
    How can I figure that out for three triangles or more? Or for K6 and above? Or for something more complicated than triangles?
  8. Aug 18, 2012 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    You cannot pick a third triangle edge-disjoint from the first two. Is that what you meant?
    Let's start with asking what is the max number of disjoint triangles that can be found from Kn. For K7, 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 Kn:
    Pick any of the nC3 triangles; there are 3 * n-3C2 ways in which the second triangle shares a vertex with the first, and n-3C3 in which it does not. Summing and halving, I get nC5(n+4)5/3.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook