# Combinatorics with different set and restrictions

I'm having two sets like

$S_1 = \{ A, B, C \}$

$S_2 = \{ D, E\}$

Within each Set I can form all possible combinations, so A,B,C,AB,AC,BC,ABC in the first case, which sums up to $2^n-1$ possibilities if I leave out zero (7 for $S_1$ and 3 for $S_2$).

However, now I'm looking for a formula to compute the number of different combinations for two (or several sets), but where I'm only allowed to take at most 1 (so 0 or 1) elements from each set. So in the example above I could take AD or CE as well as A or just D, but no AB, ABD or ADE - only no more than 1 element from the different sets.

What's a universal formula for this?

Any help is appreciated! Thanks!

-

• How many ways can you take precisely 1 element from $S_1$ and none from $S_2$?

• How many ways can you take precisely 1 element from $S_2$ and none from $S_1$?

• How many ways can you take precisely 1 element from $S_1$ and 1 from $S_2$ too?

Add these three numbers together for the total count.

-
Ok, so it'a a quick an easy n+m+n*m Thanks a lot for your help! This was not so hard, sometimes it just takes while. –  Chris C Apr 24 '12 at 6:31

There are $(n_1+1)$ choices from $S_1$ since you might choose nothing and similarly $(n_2+1)$ from $S_2$, but you have to exclude the $1$ possibility of choosing none at all, so overall $$(n_1+1)(n_2+1)-1.$$

-
A formula which generalizes easily to the case of $k$ sets, for every $k\geqslant1$. –  Did Apr 24 '12 at 7:01