Number of Combinations when order is irrelevant and there are repeated elements.

Question

Say you have a set $\{a,b,b,c\}$. Now, suppose you wanted to divide this set into two subsets of any length except for $0,4$. How would you find an answer? This question cannot be answered through traditional combinatorics formulae because of the repeated element. For example, by using the formula, nCr, the formula would count $(a,b)(b,c)$ and $(a,b)(b,c)$ as two different results even though all we did was switch the $b$'s in the two subsets. Is there any way to overcome this, and if so, can it be generalized to $n$ repeated elements? Thanks for any help.

Answer 1

If you only want to divide the multiset into two parts, this isn't difficult. Say we have $n_i$ copies of item $i$, where $1 \le i \le k$. For item $i$, we may put from $0$ to $n_i$ items in the first set, so we have $n_i+1$ choices. This gives $$\prod_{i=1}^k{(n_i+1)}$$

Now (except for one case we'll deal with laster) we have counted every possibility twice, because we counted both A, B and B, A. So we have to divide this result by $2$. Also, we have allowed the possibility that one of the sets is empty, which you specifically excluded, so we have to subtract $1$.

The one exceptional case is where each $n_i$ is even, and we put half the elements in each set. This set has not been counted twice. We need to subtract it before dividing by $2$, and then we need to add it back in.

In short, the answer is $$ \frac{\prod_{i=1}^k{(n_i+1)}}{2} -1, \text{ if any } n_i \text{ is odd },\\ \frac{\prod_{i=1}^k{(n_i+1)}-1}{2}, \text{ if all } n_i \text{ are even } $$