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 have two balls: {A, B} and 3 slots.

  • Each slot can contain one of the balls
  • Balls can repeat, e.g. {A, A, B} is ok
  • Order matters, e.g. {A, A, B} is not the same as {B, A, A}

I want to know the number of combinations that do not contain at least one A and one B.

So for the above case, the answer is 2: {A, A, A} and {B, B, B}.

I need this question answered in the general case: I have X distinct balls, and Y slot, for Y > X. Given the total number of combinations, how many combinations do not contain each of the X balls.

Thank you.

share|improve this question
    
I think you are doing great so far..just advance to three balls (A, B and C) and 4 slots (and then to 5 slots) –  jay-sun Oct 31 '12 at 21:16
add comment

1 Answer 1

Essentially you’re looking at sequences of length $Y$ over an alphabet of $X$ different symbols, and you want to count those that do not contain every symbol at least once; call these good sequences for short.

For each symbol there are $(X-1)^Y$ sequences that don’t contain that symbol, so at a first approximation there are $X(X-1)^Y$ good sequences. However, this counts many good sequences more than once: a sequence that misses both symbol $s_1$ and symbol $s_2$, for instance, gets counted once for missing $s_1$ and once for missing $s_2$. The method of inclusion-exclusion corrects for this kind of overcounting and yields the result that there are

$$\sum_{k=1}^X(-1)^{k+1}\binom{X}k(X-k)^Y$$

good sequences.

share|improve this answer
    
Wouldn't the last term (X-k) always end up being 0 for the last iteration of the summation? Should the summation only go to X-1? –  user1789509 Oct 31 '12 at 22:16
    
@user1789509: Yes, it will be $0$, so you could run the summation to $X-1$ if you wanted to do so; but since the term is $0$, it also doesn’t hurt to leave it in. –  Brian M. Scott Oct 31 '12 at 23:53
add comment

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.