3
$\begingroup$

I've tried searching around, but I think I'm not familiar with the terminology to find the correct terms to search for.

Anyways, I've run into this problem where I need to combine certain elements in groups of three - and where each combination has to fulfill some specific criteria. The criteria themselves aren't so important, but I'm stuck on creating all the different possible combinations of elements. Possibly the number of combinations is too large for me to handle the way I plan to, so any help just calculating the number of possible combinations would be helpful as well.

Problem: I have 360 elements that I want to divide into groups of 3 elements in each set. Each element is an actual physical component, so it can only be a part of one group. The order of elements in each group doesn't matter.

Since I have 360 elements and there is 3 elements in each group, this means that I'm making 120 groups. But there are many ways to arrange these groups. My problem is: 1. How many unique set of groups can I make? (Order of elements in groups and order of groups doesn't matter). 2. I feel there should be a fairly straight-forward algorithm to create all these possible sets of groups, yet I've twisted my brain all day long without finding out how. Any help would be much appreciated.

Example with fewer elements and lower group size:

Say I had 4 elements and was to group them in pairs. This means I would make 2 groups per set. If I start by giving each element just an index number, then I start with the following elements: 1, 2, 3, 4 I could then group them as follows:

Set 1: (1, 2) and (3, 4)
Set 2: (1, 3) and (2, 4)
Set 3: (1, 4) and (2, 3)

Another example:

Say I have 6 elements and want to group them in triplets. This also means 2 groups per set. So I have the following elements: 1, 2, 3, 4, 5, 6

Set 1: (1, 2, 3) and (4, 5, 6)
Set 2: (1, 2, 4) and (3, 5, 6)
Set 3: (1, 2, 5) and (3, 4, 6)
Set 4: (1, 2, 6) and (3, 4, 5)
Set 5: (1, 3, 4) and (2, 5, 6)
Set 6: (1, 3, 5) and (2, 4, 6)
Set 7: (1, 3, 6) and (2, 4, 5)
Set 8: (1, 4, 5) and (2, 3, 6)
Set 9: (1, 4, 6) and (2, 3, 5)
Set 10: (1, 5, 6) and (2, 3, 4)

But how many such sets exists if I have 360 elements to divide into groups of 3? And how do I generate the list of all those sets?

$\endgroup$
  • $\begingroup$ Incidentally, if you're looking for the best (or at least a very good) way of grouping your things, according to some scoring criterion, there are a lot of well-known optimization techniques for finding an arrangement to try and maximize some value; that's more a question of algorithms than math, but simulated annealing especially might be a fruitful direction to look at. $\endgroup$ – Steven Stadnicki Sep 11 '18 at 3:01
  • $\begingroup$ Thanks, I'll certainly look into that. As mentioned there are some criteria to each group. My priority is finding a set of groups where as many groups as possible (hopefully all, but I have some doubts) fulfill these. Optimally I'd also want to quantify each group combination and find the set of groups with the overall best results, but that might be overreaching. $\endgroup$ – Mesan Sep 11 '18 at 7:57
1
$\begingroup$

Oh boy, there are a lot more than you can probably imagine.

We want to pick a total of 120 groups. The first group, we must pick 3 elements out of the 360 that are there. There are $360\choose3$ ways to pick them, where $${n\choose k}=\frac{n!}{(n-k)!k!}$$

Next, we would pick the next group with $357\choose3$ ways, etc etc all the way down to $3\choose3$ ways.

The answer is the product of all of these terms, i.e., $$\prod_{n=1}^{120}{3n\choose3}$$Now, we can collapse some terms, since $k=3$ in each combination, and the numerator of each successive term cancels the denominator of the previous. So, the product equals $$\frac{360!}{120!\cdot(3!)^{120}}$$which has 671 digits. I'll post the pastebin for the whole number here. So no, you don't really want a list. You'd overload the entire earth's storage.

As a final note, if you have $n$ items and $k$ objects you want per group, (obviously $n$ is a multiple of $k$), the formula for the number of ways to group the elements is $$\frac{n!}{\frac nk!\cdot(k!)^{n/k}}$$

$\endgroup$
  • $\begingroup$ Thanks a lot. I think your last formula is missing something (at least I can't make it match my two examples exactly, seems to miss a division by n/k?). But you've clearly demonstrated that the number will be much to high for me to cope with the way I planned in any case. Much appreciated. Since I'm newly registered I cannot +1 you, otherwise I would. $\endgroup$ – Mesan Sep 10 '18 at 21:57
  • $\begingroup$ You are still not correct in reducing the number of permutations. It works for the 2 examples because 2/4 = 3/6 = 1/2! $\endgroup$ – Phil H Sep 11 '18 at 1:08
  • $\begingroup$ @PhilH Check my edit. Stupid oversight on my part $\endgroup$ – Don Thousand Sep 11 '18 at 2:20
  • $\begingroup$ Yes, very good. $\endgroup$ – Phil H Sep 11 '18 at 2:30
  • $\begingroup$ I believe you should have $120!$ in the denominator. $\endgroup$ – copper.hat Sep 11 '18 at 2:38
0
$\begingroup$

This is called the number of combinations in choosing $3$ from $360$ where order doesn't matter. $$(^{360}_3) = \frac{360!}{(360-3)!3!} = \frac{360!}{357!3!} = 7711320$$

Rev- sorry I misread the question. There are $360!$ ways to arrange the $360$ elements but many of them contain duplicate permutations of the $3$ elements groups so we need to divide $360!$ by $3!^{120}$. Additionally we divide by $120!$ to eliminate the 3 element group permutations. So we will have: $$\frac{360!}{3!^{120}\cdot 120!}$$

The general formula for the number of sets is therefore: $$\frac{n!}{(k!)^{n/k}\cdot (n/k)!}$$

$\endgroup$
  • $\begingroup$ Nope. He wants to pick 120 groups (-1) $\endgroup$ – Don Thousand Sep 10 '18 at 21:35
  • $\begingroup$ Rushabh Mehta is right. I don't want to find how many combinations of 3 I can make out of 360 elements, but how many different sets of such combinations I can make. $\endgroup$ – Mesan Sep 10 '18 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.