# Number of combinations that do not contain all possible inputs

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.

-
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

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$$
@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