Counting the number of combinations of elements from n sets, each containing a varied number of elements

Question

I have sets

$A = \{a_1, a_2, a_3\} $

$B = \{b_1, b_2\} $

$C = \{c_1, c_2, c_3\} $

and I'm trying to get combinations which are something like this:

$[a_1]$, $[a_1, b_1]$, $[a_1, b_1, c_1]$, $[a_1, b_1, c_2]$, $[a_1, b_1, c_3]$, $[a_1, b_2]$, $[a_1, b_2, c_1]$, $[a_1, b_2, c_2]$, $[a_1, b_2, c_3]$, $[a_1, c_1]$, $[a_1, c_2]$, $[a_1, c_3]$ and so on...

Am basically trying to get every possible combination (what is in the square brackets), where:

• It's ok if there is only one element in the square bracket
• Only one element from a set can be in a square bracket. ie: You can't have $[a_1, a_2]$
• Element pairs will never be found, reordered. ie: You'll never have
  $[a1, b1]$ and $[b1, a1]$. It will always be $[a1, b1]$ only.

I know that if there are 2 items in one set and 3 items in another set, the number of ways they can be ordered are $2\cdot 3 = 6$ ways. And the $\frac{n!}{k!(n-1)!}$ rule of combinations.

But somehow, I find it hard to get to a formula for calculating the number of possible combinations for the sets I've depicted above.

ps: This isn't a homework question.

Answer 1

There are $4$ ways of choosing an element from $A$. (One of them is not choosing at all). Similarly $3$ ways from $B$ and $4$ ways from $C$. So the total is $4 \times 3 \times 4 - 1 = \color{blue}{47}$ ways assuming that you do not want the square bracket to be completely empty.

Answer 2

Suppose (for a moment) that we allow the result to have no elements. Then you can take any one of the three elements of $A$, or no element of $A$ (four choices), then any element of $B$ or no element of $B$ (three choices), independent of the choice with regard to $A$, then any element of $C$ or no element of $C$ (four choices), independent of the choices made for $A$ and $B$.

That is altogether $4 \times 3 \times 4 = 48$ possibilities.

If we want to disallow the empty set as a possible outcome, that eliminates exactly one sequence of choices ("no element" all three times), leaving $47$ possible outcomes.