I need to know how many combinations are possible from these, if I must select at least one (but can choose more than one) from each table

Question

I have a very simple permutation question that I can't figure out on my own. So, I have

{A, B, C}

and

{D, E, F}

I need to know how many combinations are possible from these, if I must select at least one (but can choose more than one) from each table. For example, it could be (A,D), (AB,D), (ABC,D), (A,DEF), etc. (Note that, (AB,D) would mean the same thing as (BA,D).)

For {A,B} {C,D}, I know it is 9 because I manually wrote all of the possible combinations but I get stuck if its higher than 3,4.

I am trying to figure this out because although I have written code that incorporates all of the combinations I am not sure how many combinations there are. How do you solve this?

The actual tables have:

2 entries, 2 entries, 8 entries, 2 entries, 11 entries respectively. Once I figure out the basics, I will try to apply that on the actual tables.

Answer 1

It looks like you're taking a non-empty subset of each set. If a set has $n$ elements, then the number of subsets equals $\binom n0 + \binom n1 + ... + \binom nn = 2^n$.

(If you're not familiar with this formula, consider that each element can be "in" or "out" of the subset. So each element has two options, thus yielding $2^n$ possible subsets.)

But since you don't want the empty set you should subtract $1$ (since $\binom n0 = 1$). So the number of non-empty subsets of a given set with $n$ elements is $2^n - 1$.

Since your sets have, respectively, $2$, $2$, $8$, $2$, and $11$ elements, the total arrangements you're looking for is $(2^2-1)\cdot(2^2-1)\cdot (2^8-1) \cdot (2^{2} - 1) \cdot (2^{11} - 1)$.

If you have sets with $n_1, n_2, n_3,\ldots n_i$ elements, then you would have $$(2^{n_1}-1)\cdot (2^{n_2}-1) \cdots (2^{n_i}-1)$$ combinations.