Number of strings containing each vowel at least once?

Question

Consider the English alphabet {$a,b,c,...,z$}. How many strings of length $n$ can be formed in which each vowel {$a,e,i,o,u$} appears at least once?

Answer 1

The two-set version of Inclusion-Exclusion principle states that $|A\cup B|=|A|+|B|-|A\cap B|$. This can be extended to more and more terms as needed. The three-set version being $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$ and for your specific case of five sets:

$$\begin{array}{rl}|A\cup E\cup I\cup O\cup U| = &|A|+|E|+|I|+|O|+|U|\\&-|A\cap E|-|A\cap I|-\dots - |O\cap U|\\&+|A\cap E\cap I|+|A\cap E\cap O|+\dots+|I\cap O\cap U|\\&-|A\cap E\cap I\cap O|-\dots-|E\cap I\cap O\cap U|\\&+|A\cap E\cap I\cap O\cap U|\end{array}$$

That is to say, you add the size of each possible singleton, then subtract the size of each intersection of pairs of sets, then add back the size of the intersection of each triple of sets, subtracting the next size intersections, adding the next size intersections, so on so forth until you've covered all cases.

Now. Letting $A$ be the event that no $a$'s were used in the string... let us try to compute $|A|$. Well... the number of strings of length $n$ without any $a$'s are precisely those strings of length $n$ who were taken from the alphabet $\{b,c,d,e,f,\dots,x,y,z\}$. That is just an alphabet with $25$ letters. The same logic that led you to $26^n$ being the number of length $n$ strings over an alphabet with $26$ letters should lead you to the number of length $n$ strings over an alphabet with $25$ letters as being $25^n$.

The same logic will let you find $|E|,|I|,|O|,$ and $|U|$ as being the same.

Now... $|A\cap E|$ is the set of strings of length $n$ who had no $a$'s and had no $e$'s. Apply exactly the same logic as before... noting now that there are only $24$ valid letters to choose from from the alphabet.

Continue in this fashion and note how many pairs, how many triples, etc... there are to reach a final count.

$$26^n - \binom{5}{1}25^n+\binom{5}{2}24^n-\binom{5}{3}23^n+\binom{5}{4}22^n-21^n$$