\documentstyle[amstex]{article}
\input{macros-course}

\begin{document}

\psol{10}{May 1, 1997}{}

\begin{problems}

\problem Binomial Theorem
\begin{problemparts}

\ppart What is the coefficient of $x^k$ in $(x^2 + \frac{1}{x^2})^{50}$?

We know that $(x+y)^n = \sum_{i=0}^{n} {n \choose i} x^{i} y ^{n-i} $.
Applying this, we find that 

\begin{eqnarray*}
(x^2 + \frac{1}{x^2})^{50} &=& \sum_{i=0}^{50} {50 \choose i} (x^2)^{i} (\frac{1}{x^2}) ^{n-i} \\
& = & \sum_{i=0}^{50} {50 \choose i} (x^2)^{i-(n-i)}  \\
& = & \sum_{i=0}^{50} {50 \choose i} x^{4i - 2n}  \\
\end{eqnarray*}

Since we're looking for the coefficient on the $x^k$ term, let $k = 4i - 2n$,
so $i = k/4 + n/2$.
The coefficient is therefore, ${ 50 \choose k/4 + n/2}$.


\ppart Let $a,n \in \naturals$. Show that the expression
$$
\frac{1}{\sqrt{a}}[(1+\sqrt{a})^n - (1-\sqrt{a})^n]
$$
is an integer.

\begin{eqnarray*}
\frac{1}{\sqrt{a}}[(1+\sqrt{a})^n - (1-\sqrt{a})^n] & =& 
  \frac{1}{\sqrt{a}} ( \sum_{i=0}^{n} {n \choose i}(\sqrt{a})^i - \sum_{i=0}^{n} {n \choose i}(-\sqrt{a})^i)  \\
&=& \sum_{i=0}^{n} {n \choose i}(\sqrt{a})^{i-1} + 
  \sum_{i=0}^{n} {n \choose i}(-\sqrt{a})^{i-1}  \\
&=& \sum_{i=0}^{n} {n \choose i}(\sqrt{a})^{i-1} + \sum_{i=0}^{n} 
  {n \choose i}(-1)^{i-1} (\sqrt{a})^{i-1}  \\
&=& \sum_{i=0}^{n} {n \choose i}(\sqrt{a})^{i-1} (1 + (-1)^{i-1}) \\
&=& \sum_{i=0}^{n} {n \choose i}({a}^{\frac{i-1}{2}} (1 + (-1)^{i-1}) \\
\end{eqnarray*}

If $i$ is even , then $(-1)^{i-1}$ is $-1$, and $1-1 = 0$, so all terms where
$i$ is odd are $0$.

If $i$ is odd, (say $i=2k+1$), then $(-1)^{i-1}$ is $1$, and $1+1 = 2$, so
all such terms
have a non-zero, integral coefficient,  and ${a}^{\frac{i-1}{2}} = {a^k}$ is
an integer isnce $a$ is an integer.



\end{problemparts}


%inclusion/exclusion


\problem Inclusion-Exclusion
\begin{problemparts}

\ppart Prove the principle of inclusion-exclusion using mathematical 
induction.

\bigskip

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.  We will show that it is true for $n+1$ sets.

\bigskip

\begin{math}
  |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{math}

\bigskip

Next we apply the distributive law to each term involving $A_n \cup A_{n+1}$.

$$
\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 An integer is called {\bf square free} if it is not divisible 
by the square 
of a positive integer greater than $1$. Find the number of square-free
positive integers less than $100$.

$$
99 - \lfloor 99/2^2 \rfloor - \lfloor 99/3^2 \rfloor - \lfloor 99/5^2 \rfloor
- \lfloor 99/7^2\rfloor + \lfloor 99/(2^2 3^2) \rfloor = 61.
$$

\end{problemparts}


\problem Use a tree diagram to determine the number of ways that the
world series can occur, where the first team to win four games out of
7 wins the series.

\problem How many ways can a photographer at a wedding arrange 6
people in a row from a group of 10 people that includes the bride and
groom if
\begin{problemparts}

\ppart The bride must be in the picture?

\bigskip

There are $6$ ways to position the bride, $9 \choose 5$ ways to choose 
the people to appear, and $5!$ ways to arrange them.  This gives a total 
of $6\cdot 5! \cdot {9 \choose 5} = 6! \cdot {9 \choose 5}$ ways.


\ppart The bride and the groom must be in the picture?

\bigskip

There are $6$ ways to place the bride and $5$ to place the groom.  There are
$8 \choose 4$ ways to choose the people to appear and $4!$ ways to arrange them.  Total : $6! \cdot {8 \choose 4}$ ways.
 
\ppart Exactly one of the bride and groom must be in the picture?

\bigskip

$2$ ways to choose between bride or groom, $6$ ways to place them, and 
$5! \cdot {8 \choose 5}$ to choose and arrange the remaining people.
Total : $2 \cdot 6! \cdot {8 \choose 5}$ ways.


\end{problemparts}


\problem Seven women and nine men are on the faculty of a school's
math department.  How many ways are there to select a committee of 5
members if
\begin{problemparts}

\problempart at least 1 woman must be on the committee?

We need to count all possible combinations of people such that there
is at least one woman in every combination, but we must remember not
to count any combinations mutiple times.  

We can have committees with 

1 woman, 4 men: $ { 7 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 7 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 7 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 7 \choose 4} {9 \choose 1}$\\
5 women, 0 men: $ { 7 \choose 5} {9 \choose 0}$\\

So there are 
$ { 7 \choose 1} {9 \choose 4} 
+ { 7 \choose 2} {9 \choose 3}
+ { 7 \choose 3} {9 \choose 2}
+ { 7 \choose 4} {9 \choose 1}
+ { 7 \choose 5} {9 \choose 0} = 4242$ different possibilities for
committees.

Note that $7*{ 15 \choose 4} $ is not a correct answer.  
The product rule
only applies when you are choosing two separate sets of items which are
independent of each other.  
In this case, a
woman is chosen and then the remainder of the committee is chosen, but since
there may be women in the last set of $4$ chosen, we will be double counting.
For example, if $A$ and $B$ are women, and $C, D, $ and $E$ are men, then
we will count $A, \{BCDE\}$ as well as $B, \{ACDE\}$.  


\problempart at least 1 man and 1 woman must be on the committee?
We can have committees with 

1 woman, 4 men: $ { 7 \choose 1} {9 \choose 4}$\\
2 women, 3 men: $ { 7 \choose 2} {9 \choose 3}$\\
3 women, 2 men: $ { 7 \choose 3} {9 \choose 2}$\\
4 women, 1 man: $ { 7 \choose 4} {9 \choose 1}$\\

So there are 
$ { 7 \choose 1} {9 \choose 4} 
+ { 7 \choose 2} {9 \choose 3}
+ { 7 \choose 3} {9 \choose 2}
+ { 7 \choose 4} {9 \choose 1} = 4221$ different possibilities for
committees.

\problempart there must be more men than women on the committee?

For there to be more men than women, we must have $3$ or more men on the
committee.

5 men, 0 women: $ { 9 \choose 5} {7 \choose 0}$\\
4 men, 1 woman $ { 9 \choose 4} {7 \choose 1}$\\
3 men, 2 women: $ { 9 \choose 3} {7 \choose 2}$\\

$ { 9 \choose 5} {7 \choose 0}
+ { 9 \choose 4} {7 \choose 1}
+ { 9 \choose 3} {7 \choose 2}= 2772$ \\

\end{problemparts}

\problem

Five ordinary distinguishable six-sided dice are rolled.
\begin{problemparts}
\ppart How many possible ways can they land?

Five ordinary distinguishable six-sided dice can land in $6^5=7776$ ways.

\ppart How many possible ways where the sum of the first two equals the
sum of the other three?

Fix a sum $k, 3 \leq k \leq 12$.
There are $k-1 \choose k-2$ ways to form this sum with
two positive integers and  $k-1 \choose k-3$ ways to form it with $3$.
From these we must subtract the cases where the constraint $i > 6$ is violated
for die $i$.  This is equivalent to solving the equations 
$x_1+x_2 = k-6$, for $x_i >0$ and $x_1+x_2+x_3 = k-6$, for $x_i >0$. 
 So, there are
$k-7 \choose k-8$ solutions to the first equation and $k-7 \choose k-9$ to the
second equation.

So there are
$$
\sum_{k=3}^{12} \left( {k-1 \choose k-2}-{k-7 \choose k-8} \right) \cdot  
\left( {k-1 \choose k-3}-{k-7 \choose k-9} \right)
$$

where it is understood that the expressions are $0$ when not defined.

\ppart How many possible ways where there are an even number of dice coming up
even?

For each even number $k$, there are $5 \choose k$ ways to choose the dies,
$3^k$ ways to choose the numbers on them, and $3^{5-k}$ ways to choose the 
odd numbers in the remaining dice. So there are,
${5 \choose 2} \cdot 3^2 \cdot 3^3 +  
{5 \choose 4} \cdot 3^4 \cdot 3$ ways.
 
\ppart How many ways where the dice have a full house (that is, two of
one number plus three of a different number)?

 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$.

\ppart How many ways such that no pair shows?

  If they land so that no pair shows up, there are $6\times 5\times 4\times 3\times2 = 720$ possibilities.

\ppart How many ways with no two dice showing consecutive numbers?

Note this is not asking for "no two consecutive dice showing consecutive numbers"
but just no two dice showing consecutive numbers.

There are only a few combinations of values that can appear on the dice.  
These are $\{1, 3,5\}$, $\{2, 4,6\}$, $\{1, 3,6\}$, $\{1, 4,6\}$, and $\{2,5\}$.

Let's examine each of these possible combinations of values, counting
how many permutations we can get (with values repeating), and then subtract
off any permutations that we've already counted.

\begin{itemize}
\item $\{1,3,5\}$:  \\
$3^5$ possible permutations (each die can have the value 1, 3, or 5).

\item $\{2,4,6\}$:  \\
$3^5$ (no overlap with $\{1,3,5\}$). 

\item $\{1,3,6\}$:  \\
$3^5 - 3$ ($11111$ and $33333$ and $66666$ have already been counted). 

\item $\{1,4,6\}$:  \\
$3^5 - 2^5 - 1$ (All combinations of just 1 and 6 were counted in $\{1,3,6\}$.
Also $44444$ has already been counted). 

\item $\{2,5\}$: \\
$2^5 - 2$ ($22222$ and $55555$ have already been counted). 
\end{itemize}

So, all in all we have:
$3^5 + 3^5 + (3^5 - 3) + (3^5 - 2^5 - 1) + (2^5 -2) = 966$

\end{problemparts}


\problem Prove that
\[
{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}
\]
\begin{problemparts}

\ppart algebraically.

\begin{eqnarray*}
{n \choose r}{r \choose k} &= & \frac{n!}{r! (n-r)!} \frac{r!}{k! (r-k)!} \\
& =&  \frac{n! }{(n-r)! (r-k)! k!} \\
& =&  \frac{n! (n-k)!}{(n-r)! (r-k)! k! (n-k)!} \\
& =&  \frac{n!} {k! (n-k)!} \frac{(n-k)!}{(n-k-(r-k))! (r-k)!} \\
& = &{n \choose k}{n-k \choose r-k} \\
\end{eqnarray*}

\ppart using a combinatorial argument.

Lets say that we have $n$ dogs, and we wish to put some of them in two kennels.
We can fit $k$  dogs in one of the kennels and $r-k$ dogs in the other.
There are two ways we can choose which dogs to put in which kennels:  

1.  From the $n$ dogs, choose $r$ dogs which will be put into kennels:
${n \choose r}$.  
Then, from the $r$ dogs, choose $k$ dogs which will be put into the first
kennel, and put the remaining $r-k$ into the second kennel.
${r \choose k}$.  
This gives us ${n \choose r}{r \choose k} $.

2.  From the $n$ dogs, choose $k$ dogs to be put into the first kennel:
${n \choose k}$.
Then, from the remaining $n-k$ dogs, choose $r-k$ dogs which will be put into 
the second kennel: ${n-k \choose r-k}$.
This gives us ${n \choose k}{n-k \choose r-k}$.

\end{problemparts}
\problem Give a combinatorial proof that 
\[
\sum_{k=1}^n k{n \choose k}^2 = n{{2n - 1} \choose {n-1}}.
\]
Hint: count the number of ways to build a committee of $n$ people from
among $n$ math and $n$ computer science professors, assuming the chair
is a math prof.  Consider two committees different if they have different
chairs.

\bigskip

There are $n$ ways to choose a chair from the mathematicians, and then
$2n-1 \choose n-1$ ways to choose the rest of the members.

On the other hand, for a fixed number of $k$ mathematicians in the committee,
there are $k$ ways to choose the chair, $n \choose k$ ways to choose the
mathematicians, and  ${n \choose n-k} = {n \choose k}$ ways to choose the
computer scientists.  So there are $\sum_{k=1}^{n} k { n \choose k}^2$ ways
to form the committee.

\problem How many relations are there on the set $\{1,\ldots,n\}$?  How
many reflexive ones?  How many symmetric ones?  How many that are
reflexive and symmetric?

Let $S =  \{1,\ldots,n\}$, and $R$ be a relation on $S \times S$.

A relation is a set of ordered pairs, how many distinct ordered pairs do
we have to choose from?  $|S \times S| = n^2$, so there are $n^2$ 
ordered pairs.

\begin {itemize}
\item How many relations are there on the set $\{1,\ldots,n\}$?   \\

The number of distinct relations on $S$ is the number of distinct subsets 
we can make from $S \times S$.  This is the power set of $S \times S$ which
has size $2^{|S \times S|} = 2^{n^2}$.  

\item How many reflexive ones?  \\

For a relation  to be reflexive, $(x,x) \in R $  for all $x \in S$.
There are $n$ reflexive pairs, which leaves $n^2-n$ ordered pairs in
$ S \times S$.  The number of possible reflexive relations is
therefore the power set of the remaining pairs, which has 
size $2^{n^2-n}$. So there are $2^{n^2-n}$ reflexive relations.

\item How many symmetric ones?  \\

For a relation to be symmetric, for any $(a,b)$ in $R$ where $a \neq b$, 
$(b,a) $ must also be in $R$.   

Since $(x,x) \in R \rightarrow (x,x) \in R $, all the reflexive ordered pairs
are symmetric with themselves.  This means that there are $n$ reflexive ordered
pairs.

For all, $a \neq b$, if we select $(a,b)$ to be in $R$, it comes
with a partner, $(b,a)$,   
So there are $(n^2-n)/2$ sets of non-reflexive, symmetric ordered pairs 
($(a,b)$ and $(b,a)$ with $a \neq b$).  

So the number of ways of ordering these into relations is the power set of 
$(n^2-n)/2 + n = (n^2+n)/2$ items.  The size of this power set is $2^{(n^2+n)/2}$.  


\item How many that are reflexive and symmetric?\\

There are $n$ reflexive pairs, which must go into any relation, and 
$n^2-n$ other ordered pairs. These other pairs $(a,b)$ all have $a \neq b$, 
so there are $(n^2-n)/2$ symmetric pairs of ordered pairs that can be added
to any reflexive relation.  Since the power set of the symmetric pairs
of ordered pairs is $2^{(n^2+n)/2}$, that is how many reflexive, symmetric 
relations there can be.


\end{itemize}


\problem
How many graphs are there on 4 distinguishable vertices that do not
contain any cycles of length exactly 3?

\bigskip

There are ${4 \choose 2} = 6$ possible edges, so there are $2^6 = 64$ graphs
of $4$ vertices. Now we use inclusion-exclusion to compute the number of graphs
that contain cycles of length $3$. 

Let $A_i$ denote the set of graphs that have a cycle facing vertex $i$.  
For example, $A_1$ is the set of graphs containing the cycle $2,3,4,2$.
There are $4$ such sets. Each of the sets has $2^3$ elements (all the
ways to connect a vertex $i$ to the other $3$).  So,
$|A_1|+|A_2|+|A_3|+|A_4| = 4 \cdot 8 = 32$.  From this we subtract the 
number of graphs having two or more cycles of length $3$.  There are 
${4 \choose 2} = 6$ ways to pick to vertices and $2$ ways to complete each of 
the resulting graphs (by either including or excluding the remaining edge).
So there are $2 \cdot 6 = 12$ such graphs.  Then we consider the set 
consisting of intersection of three graphs containing cycles.  There are
${4 \choose 3} = 4$ ways to choose the vertices, and just one graph of this 
type ($K_4$). Finally we consider the intersection of the graphs containing 
all four cycles which consists of the single element $K_4$.
In total there are $32 - 12 + 4 - 1 = 23$ graphs containing cycles of length
$3$, so there are $64 - 23 = 41$ graphs without length $3$ cycles.
 


\problemopt Evaluate the following summation:
\[
\sum_{k=0}^m {m \choose k}/{n \choose k}
\]

\bigskip

By fixing $n$ and experimenting with a few values for $m$ a pattern arises.  we guess the identity
$$
\sum_{k=0}^m \frac{{m \choose k}}{{n \choose k}} = 1+\frac{m}{n-m+1}
$$

which we will verify by induction.

The base case for $m=0$ is trivial.

Assume that the above expression holds for some $m$.  We will show it for $m+1$.
\begin{eqnarray*}
\sum_{k=0}^{m+1} \frac{{m+1 \choose k}}{{n \choose k}} \\
& = & \frac{{m+1 \choose 0}}{{n \choose 0}} + 
\sum_{k=1}^{m+1} \frac{{m+1 \choose k}}{{n \choose k}} \\
& = & 1+ \sum_{k=1}^{m+1} \frac{\frac{m+1}{k}}{\frac{n}{k}}
\frac{{m \choose k-1}}{{n-1 \choose k-1}} \\
& = & 1 + \frac{m+1}{n} \sum_{k=0}^{m} \frac{{m \choose k}}{{n-1 \choose k}}\\
& = & 1 + \frac{m+1}{n} \left(1+\frac{m}{n-m} \right)\\
& = & 1+\frac{m+1}{n-m}\\ 
\end{eqnarray*}

which is the desired expression.

\end{problems}

\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 







