Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

  • 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.

share|improve this answer
    
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.$$

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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