I am studying for an upcoming test and I was having trouble with this practice problem:
Consider strings consisting of 12 characters, each character being a, b, or c. Such a string is called valid if at least one of the characters is missing. For example, abababababab is a valid string, whereas abababacabab is not a valid string. How many valid strings are there?
I think the number of strings is equal to $2^{12}$ because the string is only valid if 2 characters in 12 positions.
Is my solution to the question correct?
Thanks
$\endgroup$ 12 Answers
$\begingroup$$2^{12}$ is the number of strings that contain only $a$ and $b$. There are other strings that contain only $a$ and $c$, and other strings that contain only $b$ and $c$.
However, you cannot simply add the number of strings of the above 3 sets, as some strings fall into more than one of the above sets, thus being counted more than once. For one example, consider $aaaaaaaaaaaa$.
Try to form a Venn diagram to see how some strings are counted multiple times.
You can also calculate using the inclusion-exclusion principle. If you let $A_1$ be the set of strings not containing $a$, $A_2$ be the set of strings not containing $b$, and $A_3$ be the strings not containing $c$, then the required answer is
$$\left|\bigcup_{i=1}^3 A_i\right| = \sum_{i=1}^3\left|A_i\right| - \sum_{1\le i<j\le 3}\left|A_i\cap A_j\right| + \sum_{1\le i<j<k\le 3}\left|A_i\cap A_j\cap A_k\right|$$
In this formula, for example, $A_1\cap A_2$ is the set of strings not containing both $a$ and $b$. And you should be able to find out all of the 7 set sizes to get your answer.
$\endgroup$ $\begingroup$$2^{12}$ correctly counts the number of strings of length 12 consisting of $a$ and $b$, e.g. $ababababababababababbb$. Is this all that you want to count though?
$\endgroup$
