\problemdata                                                             
        {Counting substrings} % latex-friendly label for the prob.
        {Couting, inclusion exclusion} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz 2, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           

How many $6$-digit natural numbers are there that do not contain
``$123$'' or ``$456$'' as a subsequence? (for purposes of this problem
numbers may have leading $0$'s, so the 6-digit natural numbers are
$000000$, $000001$, $\ldots$, $999998$, $999999$).

\bigskip
\solution{ 
Let
\begin{itemize}
\item $A$ be the set of all six-digit strings, using the digits
$\{0, 1, \ldots, 9\}$.
\item $B$ be the set of six-digit strings that contain the subsequence
$123$.
\item $C$ be the set of all six-digit strings that contain the subsequence
$456$.
\item $D$ be the set of all six-digit strings that do not contain 
$123$ or $456$.
\end{itemize}
We're interested in figuring out $| D |$.
Since $$D = A - (B \cup C),$$
and $B \cup C \subseteq A$,
we can use the inclusion-exclusion formula:
$$| D | = | A | - |B \cup C| = | A | - | B | - | C | + | B \cap C |.$$

First, $|A| = 10^6$, since we can put any of ten digits in each of
six places.  

Now, a string can contain $123$ in any of four positions; once this
position is chosen, we have $1000$ choices for the remaining positions.
However, this approach counts the string $123123$ twice, so 
the total size of $B$ is
$$| B | = 4(1000) - 1 = 3999.$$
By the same reasoning, we get
$$| C | = 3999.$$

Finally, there are only two strings in $B \cap C$, namely $123456$ 
and $456123$.  Thus,
$$| B \cap C | = 2.$$
Plugging this into our formula, we get
$$| D | = 10^6  - 3999 - 3999 + 2 = 992004.$$


By far the most common error was to fail to adjust for the overcount 
of the sequences $123123$, $123456$, $456123$, and $456456$.  Some 
students did not allow for repetition of digits or tried to 
compute permutations of some digits using factorials.
}

\end{problem}                                 