# 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

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.

– Tim
Commented Apr 18, 2016 at 21:24
• As @Tim said, you should clarify whether the order of the selections matter - is "ABC" different to "BAC"? Commented Apr 18, 2016 at 21:26
• Are combinations like (A,D,B) or (AE,C) allowed? Commented Apr 18, 2016 at 21:27
• @Silverfish No, the order doesn't matter. Commented Apr 18, 2016 at 21:28
• @RustyStatistician yea but (A,D,B) would be considered the same thing as (A,B,D) or (D,B,A) Commented Apr 18, 2016 at 21:28

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.

• You've forgotten ABCD. Commented Apr 18, 2016 at 22:10
• In your solution, does the order matter? In my case, the order shouldn't matter and they are considered equal. Commented Apr 18, 2016 at 23:07
• No, order doesn't matter. The $2^n$ subsets of a set with $n$ elements is the number of subsets without regard to order. Commented Apr 18, 2016 at 23:21