\problemdata                                                             
        {Counting digits} % latex-friendly label for the prob.
        {complement, stars and bars} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz 2, 7} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
For each of the following problems, determine the value or expression
requested.  Briefly justify your answers.

\begin{problemparts}

\problempart How many of the billion numbers in the range from 1 to and including
1,000,000,000 contain the digit~$1$?  
(\hint Don't do inclusion/exclusion.)
\medskip
\bigskip

\solution{
We can count up how many DO NOT contain the digit 1 and subtract:

(Total Number) - (number without 1's) 

$1,000,000,000 - (9^9 - 1) = 612,579,512$

(the minus is for 0 which is not in our range)
}

%\vspace{1in}
\problempart Consider the set of $10^n$ $n$-digit integers (where leading
0's are permitted).  Consider two integers to be equivalent if the
digits of one are a permutation of the digits of the other.  How many
equivalence classes of the $10^n$ $n$-digit integers are there? 

\solution{

Here, we can use a stars and bars idea.  Let there be 9 bars for each number from 0-9.  There are n stars for the number of digits.  

$ 9+n \choose n $
} 

%\vspace{1in}

\problempart How many ways are there to order the 26 letters of the alphabet
so that no two of the vowels {\tt a}, {\tt e}, {\tt i}, {\tt o}, {\tt
u} appear consecutively and the last letter in the ordering is not a vowel?  

\solution{

Here, we can again use a stars and bars idea.  We can let the 21 bars
be the consonant letters in the alphabet.  We can let our 5 stars be
the vowels.  Now, we must choose 5 places to place our stars such that no
two stars are next to each other.  We simply choose 5 out of 21 of our bars
and stick our stars to the left of each of the chosen bars.  Once we have
choosen these, we can order the vowels and consonants as we like.

$ 21 \choose 5$ $ \cdot 21! \cdot 5! $
}
%\vspace{1in}
\problempart How many ways are there to order the 26 letters of the alphabet
so that there are {\em at least two} non-vowels between any pair of vowels,
and the last two letters in the ordering are not vowels? 
\solution{

Glue two consonants to the right of every vowel. Let these object be
the bars and the remaining consonants be the bars. There are 11
remaining consonants, i.e., stars, and 5 bars. Therefore, there are
\begin{displaymath}
  \binom{16}{5}
\end{displaymath}
ways to arrange the stars and bars. Each such arrangement corresponds
to a unique ordering of vowels and consonants. To count the number of
orderings of letters, we need to multiply this by $5!21!$ since there
are 5~vowels and 21~consonants. So, the final answer is
\begin{displaymath}
  \binom{16}{5}5!21! = \frac{16!21!}{11!}\,.
\end{displaymath}


Common errors: These all required some insight into the problem and
were very difficult to do if you attempted some other method
(especially inclusion/exclusion).  The most common mistakes beyond
that were to forget about 0 in part a or to not order the cards in
parts c and d.
}

\end{problemparts}
\end{problem}
                                 