Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sorry if the title isn't proper math-talk. Hopefully I can explain it better here.

So let's say we have a set. 1, 2, 3, 4, 5, 6, 7, 8, 9. I want to know how many groups of three can be made where no two sets have two items in common.

If (1,2,3) is one group, then no other group can have (1,2), (1,3), or (2,3).

So for nine items we can make:

123 
145 
167
189
246
258
269
348
379
478

Ten groups that follow those rules.

What about n items?

Hopefully this question is something fun!

share|improve this question
1  
In your example you do have a repeat: (4,8) –  Josh B. Mar 31 at 1:31
    
You can do better though, with n=9 it's possible to find 12 sets of 3 which don't have any overlapping pairs. This covers all possible pairs. Google "Steiner Triple Systems" for some relevant info. –  Josh B. Mar 31 at 1:34
1  
You're right, Josh! That's what I get for not knowing how the actual math works. I looked it up, but I don't really follow. I'm only in my second year of college math. –  alsfnkasjdfnkasjbfoiuewb Mar 31 at 1:54
    
So, Josh, is there no simple formula that takes the number of items and produces the number of triplets? –  alsfnkasjdfnkasjbfoiuewb Mar 31 at 1:58
1  
The problem is really covering the complete graph on n vertices with as many triangles as possible. I believe this is the right sequence, A001839 –  Josh B. Mar 31 at 2:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.