If I had the numbers [2,2,2,2,3,3] and I wanted to find the number of ways to split them into two groups, then how would I do it.
I know that if I had all different numbers eg.[1,2,3,4,5,6] then I would have three ways of making groups, having groups of size [1 and 5] then [2 and 4] then [3 and 3]. Therefore, to find all the ways of splitting them into groups, I would simply do $${6 \choose 1} + {6 \choose 2} + {6 \choose 3}=6+15+20=41$$
However, how can I do it with numbers like those specified at the start, where I have repeats.
The overall question is like this:
I have a list of numbers, several of which are repeats. I want to find the number of ways in which I can split them into x groups so that the product of the groups in each case is different eg. for my initial example the groups [2,3,3][2,2,2] and [3,3,2][2,2,2] are the same-I want combinations not permutations. Also, by needing different products each time, there are some cases which I have to remove.
I want to know if there is a formula of the number of ways in which a list of numbers(containing repeats) can be split into x groups, of any size>1, such that the products of each group in the set of groups is different. the example is of course [2,2,2,2,3,3] and the answers would be:
[2] and [2,2,2,3,3]
[3] and [2,2,2,2,3]
[2,2] and [2,2,3,3]
[2,3] and [2,2,2,3]
[3,3] and [2,2,2,2]
[2,2,2] and [2,3,3]
[2,2,3] and [2,2,3] (However this can be discounted because products are 12 and 12)
This leaves 6 answers.
If you find any of this question unclear, comment and I will clarify it for you.
Thanks in advance for your help!
Best Answer
Leaving aside the product restriction for now, you can consider the ways to split each number separately. With four twos, you have five choices for how many are on the left. With two threes, you have tree choices for how many are on the left. This gives $5 \cdot 3=15$ choices, but we subtract two because all the numbers on the same side is not allowed. We have counted each division twice except for those which have exactly half the numbers on each side. That is possible here. It is exactly the case where the products will be equal. We delete that case and divide by two to get the six cases you found. If you have $a_1$ of the first number, $a_2$ of the second, etc. there will be $$\frac 12\left(\prod (a_i+1)[-1]\right)-1$$ where the $[-1]$ applies if all the $a_i$ are even and the last $-1$ removes the case where one group is even.
This will be fine as long as there is no way to make a case with matching products unless we split the numbers evenly, such as the numbers being distinct primes. If your list were $[2,2,2,2,4,4]$ we would have other combinations to exclude and you would just have to compute.