2
$\begingroup$

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.

  • 0
    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)2012-10-31

1 Answers 1

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.

  • 0
    @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.2012-10-31