# Given a number of items, how many sets of three are there where no two sets are two thirds similar?

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.

Hopefully this question is something fun!

-
In your example you do have a repeat: (4,8) –  Josh B. Mar 31 '14 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 '14 at 1:34
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 '14 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 '14 at 1:58
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 '14 at 2:21