2
$\begingroup$

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.

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.