I recently solved a task on Stackoverflow. Please see here
Out of an array with 9 values, triplets consisting of 3 distinct values shall be generated. Calculating them is simple. Result is n choose k, 9 choose 3 = 84 triplets.
Next I needed to select 3 triplets, a triplet set, out of this set of 84 triplets where all values in the triplet set are also distinct. No double value anywhere.
Overall sets of triplets could again be calculated by n choose k, 84 choose 3 triplets = 95284 triplet sets. But, with the condition that all values in the triplet set should be distinct.
As a result I got 280 triplet groups (Via brute force).
Now, I do not know, if this number 280 is correct.
- How can this value be calculated?
- And how can the groups be calculated without brute force?
Best Answer
An argument which avoids "division by symmetry":
Notice that we can apply an order to the elements in our set. Without loss of generality then, suppose our elements in the set were explicitly $\{1,2,3,\dots,9\}$
Now, decide what other two elements will be in a triple with the element $1$. Have these form the first triple and remove these from the list of still available elements.
Next, regardless what we chose in the previous step there will be some smallest remaining element. Whatever that happened to be take that and choose two more of the remaining elements to form the next triple.
The final triple will be whatever remains.
This gives a count of:
$$\binom{8}{2}\binom{5}{2} = 280$$