[Math] Possible combinations of two sets of three into a set of two

combinatoricsdiscrete mathematics

I'm trying to find the mathematical term for a certain phenomenon and hopefully a more general way to solve such problems. Say there are two sets, each $= \{A, B, C\}.$ I would like to know how many different possible ways I can combine these sets into a set of two $\{…,…\}.$ The combination $\{A, B\}$ is considered the same as $\{B, A\}.$ The only way I can think to do this, is:

$$ 3*3 – \binom{3}{2} = 6 $$

Basically, I am counting up the total number of possible combinations (3*3) and subtracting out the combinations I overcounted. Is there a name for this kind of a calculation? Is there anyway to describe this more mathematically, as opposed to this intuitive approach?

Thanks!

Best Answer

You are actually counting the number of subsets of $\{A,B,C\}$ of a fixed size ($2$, in your example), without regarding order, and allowing duplicates. A more general way to look at it, is taking some set $A=\{1,\ldots,n\}$, and trying to assign a number of occurrences to each of $1\ldots n$, that is, "$1$ appears once, $2$ appears five times, etc.", while demanding that the sum of these numbers be some constant $k$ - that is, you're only selecting a set of $k$ elements.

This is equivalent to the following situation:

You have $n$ buckets and $k$ balls. You wish to toss the balls into the buckets, putting as many balls in one bucket as you like. In order to calculate the number of ways to do that, it's more convenient to look at the $n$ buckets as $n-1$ partitions - defining $n$ different spaces, that you can place among the balls, like in the following illustration:

$$\cdot|\cdot\cdot\cdot||\cdot|\cdot\cdot||$$

This has $7$ buckets, with $1,3,0,1,2,0,0$ balls respectively.

Now we can give a general equation.

Sort the partitions and the balls together - there are $(n-1+k)!$ ways to do that.

Disregard the internal ordering of the partitions and the internal ordering of the balls, as you're only interested in the number of balls in each "bucket", and the "buckets" are defined by their position regardless of which partitions surround them.

Therefore, the number of ways to select a set of size $k$, with duplicates allowed and without regarding order, from a set of size $n$ is $\frac{(n+k-1)!}{(n-1)!k!}=\binom{n+k-1}{k}$.

In your particular case, $n=3$ and $k=2$, so this equals $\binom{4}{2}=6$.

Related Question