\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

%\addtolength{\topmargin}{-.35in}
%\setlength{\textheight}{9.1in}


\begin{document}

\psol{8}{November 7, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Undirected graphs}

In an undirected graph on $n$ vertices, an edge is an unordered pair of
vertices, so there are ${n \choose 2}$ possible edges.
Each possible edge is either present or absent, so there are $2^{n \choose 2}$
possible undirected graphs on $n$ vertices.

\problem {\bf Distinguishable dice}

Five ordinary distinguishable six-sided dice can land in $6^5=7776$ ways.  If
they land so that no pair shows up, there are $6\times 5\times 4\times 3\times
2 = 720$ possibilities.  To get a full house, there are ${5 \choose 2}$ ways to
pick which dice are the pair and which are the triple, and $6\times 5$ ways to
choose the values of the pair and triple: ${5\choose 2}\times 6\times 5 = 300$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Coefficient}

By the binomial theorem, the typical term in this expansion is
${100\choose j} x^{100-j}(1/x)^j$, which simplifies to 
${100\choose j} x^{100-2j}$.
As $j$ runs from $0$ to $100$, the exponent runs from $100$ down to $-100$  
in decrements of $2$. If we let $k$ denote the exponent, then solving
$k=100-2j$ for $j$, we obtain $j=(100-k)/2$. Thus the values of $k$ for 
which $x^k$ appears in this expansion are 
$-100, -98,\ldots, -2, 0, 2, 4,\ldots, 100$, and for such values of $k$
the coefficient is ${100\choose {100 - k\over{2}}}$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Filenames}

\begin{problemparts}
\problempart $52^4 = 7311616$.
\problempart $52^4 \div 2^4 = 456976 = 26^4$.
\problempart $\sum_{i=1}^4 52^i = (52^5-52)/(52-1) = 7454980$; $\sum_{i=1}^4
26^i = (26^5-26)/(26-1) = 475254$.  The division rule can be applied only to
the individual terms of the summation.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Balls and urns}

\begin{problemparts}
\problempart $3\cdot 3\cdot 3\cdot 3=81$.
\problempart 14.
We can put either all 4 balls in one urn,
3 in one, 2 in one and 2 in another, or 2 in one and 1 in each of the other
two.  The balls are distinguishable, so there are $4\choose 3$ ways of
putting 3 in one.  There are $4\choose 2$ ways of putting 2 in one and 1 in
each of the other two.  There are ${4\choose 2}/2$ of putting 2 in one and
2 in another.
So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} = 14.
\]
\problempart 15.
Create 6 slots and choose 2 to contain bars leaving
$r_1, r_2$ and $r_3$ consecutive
slots with stars with $r_1+r_2+r_3=4$.  This corresponds
to putting $r_i$ balls in urn $i$.  So the answer is ${6\choose 2}=15$.
\problempart 
4.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 3 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset$, or
$\{1,1,1\}, \{1\}, \emptyset$, or
$\{1,1\}, \{1,1\},\emptyset$, or
$\{1,1\}, \{1\}, \{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf Integers not divisible}

Here we use inclusion-exclusion to count the number of integers from 1 to 1000
not divisible by 6, 10, or 15.  Make a table, and add the numbers with
appropriate signs:

\medskip

\begin{tabular}{|c|r|r|c|}
\hline
divisible by & least common multiple & number of integers & include/exclude \\
each of      & of divisors           &from 1 to 1000     & $+/-$\\
\hline
\hline
          &   1 & 1000 & $+$ \\
6         &   6 & 166 & $-$ \\
10        &  10 & 100 & $-$ \\
15        &  15 &  66 & $-$ \\
6, 10     &  30 &  33 & $+$ \\
6, 15     &  30 &  33 & $+$ \\
10, 15    &  30 &  33 & $+$ \\
6, 10, 15 &  30 &  33 & $-$ \\
\hline
\end{tabular}

\hspace{3in} These add up to 734.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf Binomial coefficient identity}

\begin{problemparts}
\problempart 
\begin{eqnarray*}
x^{-n}(1+x)^n x^n (1+x^{-1})^n &=& x^{-n}(1+x)^n (x+1)^n \\
(1+x)^n (1+x^{-1})^n &=& x^{-n}(1+x)^{2n}\\
\sum_{i=0}^n {n\choose i}x^i \sum_{j=0}^n {n\choose j}x^{-j} &=& x^{-n}\sum_{i=0}^{2n} {2n\choose i}x^i\\
\sum_{i=0}^n {n\choose i}^2 &=& {2n\choose n}
\end{eqnarray*}
by equating the coefficients of $x^0$.

\problempart
Suppose we have $2n$ objects, $n$ of which are red, and $n$ of which are blue.
How many ways can we pick $r$ red ones and $n-r$ blue ones?  Clearly this is
$${n \choose r} {n \choose n-r} = {n \choose r}^2.$$  How many ways can we choose $n$ objects
total, regardless of how many are of each color?  This is just 
$$ \sum_{r=0}^n {n \choose r}^2.$$  But there are  ${2n \choose n}$ ways to
choose $n$ objects, so these must be the same number.
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf Inclusion-Exclusion Principle}

\bparts

\ppart The base case is $n=2$, for which we already know the formula to 
be valid. Assume that the formula is true for $n$ sets. Look at a 
situation with $n+1$ sets, and temporarily consider $A_n\cup A_{n+1}$ as
one set. Then by the inductive hypothesis we have

\begin{eqnarray*}
|A_1\cup \ldots \cup A_{n+1}| &=& \sum_{i<n}{|A_i|+|A_n\cup A_{n+1}|-\sum_{i<j<n}{|A_i\cap A_j|}} \\
&-& \sum_{i<n}{|A_i\cap(A_n\cup A_{n+1})|+\ldots + (-1)^n|A_1\cap \ldots \cap A_{n-1}\cap(A_n\cup A_{n+1})|}
\end{eqnarray*}

Next we apply the distributive law to each term on the right involving 
$A_n\cup A_{n+1}$, giving us

\[
\sum{|(A_{i_1}\cap \ldots \cap A_{i_m})\cap(A_n\cup A_{n+1})|} = 
\sum{|(A_{i_1}\cap \ldots \cap A_{i_m}\cap A_n)\cup (A_{i_1}\cap \ldots \cap A_{i_m}\cap A_{n+1})|}.
\]

Now we apply the base case to rewrite each of these terms as

\[
\sum{|A_{i_1}\cap \ldots \cap A_{i_m}\cap A_n|} + \sum{|A_{i_1}\cap \ldots \cap A_{i_m}\cap A_{n+1}|} - \sum{|A_{i_1}\cap \ldots \cap A_{i_m}\cap A_n\cap A_{n+1}|},
\]

which gives us precisely the summation we want.

\ppart Square-free numbers are those not divisible by the square of a prime. 
We count them as follows: 
\[
99-\floor{99/2^2}-\floor{99/3^2}-\floor{99/5^2}-\floor{99/7^2}+\floor{99/(2^23^2)}=61.
\]
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}

