Finding Number of Unique Combinations, Multiple n-sizes, Multiple Sets

Question

Excuse me if my terminology is not precise.

Suppose I have two containers containing $x$ and $y$ objects respectively. The objects in each container are all different.

I am looking for the number of unique combinations when required to pull objects from both containers, assuming that a combination must include at least one item from each container. One complexity comes from the idea that a "unique combination" can include all possible scenarios by which someone could pull any number of objects between 1 and $x$ for container one, paired with any number of objects between 1 and $y$ for container two.

The other complexity stems from the idea that I want to eliminate instances where a mere reshuffling would produce another arrangement to count -- in other words, I would not consider a draw of $A,B,C$ from the first container and $X,Y,Z$ from the second one, to be different from a draw of $B,C,A$ from the first one and $Y,Z,X$ from the second. Both of these, for my purpose, would constitute only one unique instance.

Question: Is there a well-known method to solve for the number of unique combinations pulling from both containers, given that I'm not only looking for a "pair," "group of 3," "group of 4," etc.? One should also note, if not already obvious, that the number of objects in each container ($x$ and $y$) are not equal.

Thanks in advance!

Answer 1

I think the answer should be $$\binom{x}{1}\bigg[\binom{y}{1}+\binom{y}{2}+...+\binom{y}{y}\bigg]+\binom{x}{2}\bigg[\binom{y}{1}+\binom{y}{2}+...+\binom{y}{y}\bigg]+...+\binom{x}{x}\bigg[\binom{y}{1}+\binom{y}{2}+...+\binom{y}{y}\bigg]$$ $$=\bigg[\binom{x}{1}+\binom{x}{2}+...+\binom{x}{x}\bigg]\cdot\bigg[\binom{y}{1}+\binom{y}{2}+...+\binom{y}{y}\bigg]$$ $$= (2^x-1)\cdot (2^y-1)$$ since all objects are different from each other. So we can simply seperate the problem to cases where we draw $1$ object from the first container and draw $1$ object to $y$ objects from the second container. Then next case is where we draw $2$ objects from the first container and draw $1$ object to $y$ objects from the second container, again. Continuing with a similar argument gives us the above result.

$\big($Notice that we also use the fact $\binom{n}{0}+\binom{n}{1}+...+\binom{n}{n} = 2^n\big)$

If it asks combinations but not permutations, then ordering is not important so $\{A,B,C,X,Y,Z\}$ is same as $\{B,C,A,Y,Z,X\}$.

SOME TERMINOLOGY AND NOTATION:

• In general, $\{...\}$ is used for unordered tuples (combinations) while $(...)$ is used for ordered tuples (permutations).

• When we have more than two ordered or unordered objects, say $n$ many of them, we generally call them $n$-tuple.

Answer 2

$$\sum_{i=1}^x \binom{x}{i}\Big(\sum_{j=1}^y \binom{y}{j}\Big)=\sum_{i=1}^x \binom{x}{i}\sum_{j=1}^y \binom{y}{j}$$

The right side of the equality is probably the easier way to think about this-- it just multiplies the total number of nonempty sets you can choose from X by the total number of nonempty sets you can choose from Y (product rule!).

The left hand side counts the same thing in a slightly different manner (fix some $i$, multiply the number of ways to choose $i$ by the number of ways to choose each $j$...).

Indeed, this just becomes $$\sum_{i=1}^x \binom{x}{i}\sum_{j=1}^y \binom{y}{j}=(2^x-1)(2^y-1),$$ as written by ArsenBerk, since there are $2^x$ total subsets of X and $2^y$ total subsets of Y* , and removing the one empty set that is counted gives us $(2^x-1)$ nonempty subsets of X and $(2^y-1)$ nonempty subsets of y.

*One way to see that this is $2^y$ is to notice that, when forming a subset, you choose for each of the $y$ elements of Y whether it will 1) be in the subset or 2) not be in the subset. There are $2$ choices for each element, and hence, by the product rule, there are $\underbrace{2 \cdot 2\cdot 2 \cdots 2}_{y \text{ times}}=2^y$ possibilities.