How to calculate the number of strings using Inclusion-Exclusion method?

Question

I have difficulties in solving the following problem using the Inclusion-Exclusion method. How many strings of length n >= 3 are there which can be built using A,B,C,D,E , where A occurs at least once, B occurs at least once and C occurs at least once?

I started like this: The number of all possible strings is 5^n . The number of all possible strings without A is 4^n , the number of all possible strings without B is 4^n and the number of all strings without C is 4^n. That means that now I have to do the following: 5^n - 3*4^n Now I am stuck and don't know how to go on..

Any help will be appreciated, thank you!

Answer 1

Consider a string that has neither A nor B: it got counted once in the original $5^n$, and it was subtracted twice, once because it has no A, and once again because it has no B. Thus, the calculation $5^n-3\cdot4^n$ counts it a net total of $-1$ times. You want to count it $0$ times, so you need to add it back in. How many such strings are there? Clearly these are $3^n$ of them, so we need to add $3^n$. The same argument applies to the strings that are missing both A and C, and to the strings that are missing both B and C, so actually have to add back in $3\cdot3^n$: one $3^n$ for the strings missing A and B, another for those missing A and C, and a third for those missing B and C.

At this point our provisional result is $5^n-3\cdot4^n+3\cdot3^n$. However, there are $2^n$ strings that are missing A, B, and C, and we should check whether they’re being counted correctly. Each of them is counted once in $5^n$; subtracted $3$ times in the $-3\cdot4^n$ term, once for missing A, once for missing B, and once for missing C; and added back in $3$ times in the $3\cdot3^n$ term, once for missing A and B, once for missing A and C, and once for missing B and C. Thus, each of these strings has been counted a net total of $1-3+3=1$ time, when we want it to be counted just once. Clearly we should subtract $2^n$ to fix this, giving us

$$5^n-3\cdot4^n+3\cdot3^n+2^n$$

strings with at least one each of A, B, and C.

The inclusion-exclusion principle actually has a much more general form, and its proof requires a little mathematical sophistication, but the underlying idea in its simplest form is what I’ve tried to explain here: the alternating terms correct for successive over- and undercounting of the set in which we’re interested.

Answer 2

According to the inclusion-exclusion principle, you have to compute the following values:

• how many strings where a specified letter appears at least once: since the letter can appear in any position, this will be $n\cdot5^{n-1}$.
• how many strings where two specified letter appears at least once: the two letters cannot occupy the same position, thus this will be $$ \frac{n!}{(n-2)!}5^{n-2} $$
• total number of strings: $5^n$.

Then, you obtain that the total number of strings in which $A$, $B$, $C$ appear at least once is

$$ 5^n - 3\cdot n\cdot5^{n-1} + 3 \frac{n!}{(n-2)!}5^{n-2} = 5^{n-2}(n^2 -16n + 25). $$