\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
%\usepackage{latexsym}
%\usepackage{graphics}
\input{macros-course}

\renewcommand{\solution}[1]{}

\begin{document}
\pset{9}{November 5, 1999 (revised 11/6)}{Friday, November 12, 1999 at start of tutorial}

\textbf{Required reading}: F97 Lecture Notes 15, 16.  Rosen 4.3, 4.6.

\textbf{Optional Reading}: Tutorial Notes from Fall 1997, 10/24.

Remember to include a \textbf{collaboration statement} on the front page
of your solutions.

\begin{problems}

\problem We consider simple graphs with $n$ distinctly labeled vertices.

\bparts
\ppart 
How many complete graphs are there on these $n$ vertices?

\solution{One.}

\ppart How many simple paths\footnote{We use the definition of simple path
from the notes: a path with no repeated vertex.}
of length $i$ are there in the complete graph
with $n$ vertices.

\solution{

A path is determined by the order in which vertices occur.  In the
complete graph all vertices are connected by an edge, so the number of
simple paths of length $i$ ($1 \leq i \leq n$), is the same as the number
of $i$-permutations of the $n$ vertices, namely, $P(n,k) \eqdef
n!/(n-i)!$.

}

\ppart How many simple \emph{cycles} of length $i$ are there in the
complete graph?  (A simple cycle is a ``circular'' simple
path.)

\solution{

Each simple cycle can be represented by the unique sequence of $i$
vertices on it, starting at some vertex and picking a direction to go
around the cycle.  There are $i$ vertices at which to start and two
choices of direction, so each cycle can be represented by exactly $i \cdot
2$ of the $P(n,i)$ sequences vertices of length $i$.  Hence the number of
simple cycles of length $i$ is $P(n,i)/2i$.

}

\ppart
How many such distinctly labelled $n$-vertex graphs are there?

\solution{

$2^{\binom{n}{2}}$.  For each possible edge, we choose whether it's in the
graph or not.

}

\eparts

\problem \textbf{r-Combinations.}
% Based on Example given in Introductory Combinatorics (Brualdi), pg. 62

How many 7-letter English words can be constructed using the 26 letters of the
alphabet if each word contains 2,3, or 5 vowels?  There is no
restriction on the number of times a letter can be used in a word.

\solution{Let us count the number of words according to the number of
vowels they contain and then sum them up using the sum rule.
There are 5 vowels and 22 cononants.

\textit{2 vowels}: The 2 positions occupied by the vowels can be chosen in
$\binom{7}{2}$ ways; the other 5 positions are occupied by consonants.
The vowel positions can then be completed in $5^2$ ways and the consonant
positions in $21^5$ ways.  Thus the number of words with 2 vowels is
\[\binom{7}{2}5^2 21^5 = \frac{7!}{2!5!}5^2 21^5 \]

\textit{3 vowels}: \[\binom{7}{3}5^3 21^4 = \frac{7!}{3!4!}5^3 21^4 \]

\textit{5 vowels}: \[\binom{7}{5}5^5 21^2 = \frac{7!}{5!2!}5^5 21^2 \]

Hence the total number of words is \[\frac{7!}{2!5!}5^2 21^5 + \frac{7!}{3!4!}5^3 21^4 + \frac{7!}{5!2!}5^5 21^2 \]}


\problem \textbf{r-Combinations with repetitions.}
% 

\bparts 

\ppart The coffee shop in building 4 has 15 kinds of donuts
available. The number available is not infinite, but we assume it's
large enough that I can buy any 10 I wish. How many different
combinations of 10 donuts can I buy?

\solution{Each combination of 10 donuts is a 10-combination from a
       multiset having 15 kinds of objects. The number of such
       combinations is $\binom{10+15-1}{10} = \binom{24}{10}$.}

\ppart Now suppose I'm going to buy 20 donuts, and I want to make sure
to buy at least one of each of the 15 kinds.  How many collections of
20 are possible?

\solution{First choose one of each kind: that's 15 doughnuts. Now I
       choose a 5-combination to complete the set. I can do that in
       $\binom{5+15-1}{5} = \binom{19}{5}$ ways.  No wonder it takes
       so long to get out of the coffee shop...}

\ppart More donuts... What if I'm going to buy 20 donuts, and I want
to be sure to get 5 glazed and 6 old-fashioned donuts. The rest can be
anything. How many possible ways are there for me to do so?

\solution{Choose the 5+6 we really want first, and then choose a
       9-combination for the rest. We can do this in $\binom{9+15-1}{9}
       = \binom{23}{9}$ ways.}

\eparts


\problem \textbf{Pascal's Triangle.  }

Let us redraw Pascal's Triangle in the following way:

\begin{center}
\begin{tabular}{lcccccccc}
$1$ \\
$1$ & $1$ \\
$1$ & $2$ & $1$ \\
$1$ & $3$ & $3$ & $1$ \\
$1$ & $4$ & $6$ & $4$ & $1$ \\
$1$ & $5$ & $10$ & $10$ & $5$ & $1$ \\
$1$ & $6$ & $15$ & $20$ & $15$ & $6$ & $1$ \\
$\cdot$ & $\cdot$ & $\cdot$ & $\cdot$ & $\cdot$& $\cdot$  & $\cdot$ & $\cdot$ \\
\end{tabular}
\end{center}

Now let n be a nonnegative integer and let k be an integer with $0
\leq k \leq n$.  Define $path(n,k)$ to be the number of paths from the
top left corner (the entry $\binom{0}{0} = 1 $) to the entry
$\binom{n}{k}$, where each path is composed of only two possible types of
moves: 

type $(a)$: from any entry in the Triangle we can move to the entry immediately below the current entry (i.e. in the next row) 

type $(b)$: from any entry in the Triangle we can move to the entry
immediately below and to the right of the current entry (i.e. in the next row).

 We define $path(0,0)=1$.  Prove that the value of an entry 
$\binom{n}{k}$ of Pascal's
triangle represents $path(n,k)$, the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.

\solution {
Notice that $path(n,0)=1$, (we must move straight down to reach $\binom{n}{0}$) and $p(n,n)=1$, (we must move diagonally to reach $\binom{n}{n}$).

Observe that each path from $\binom{0}{0}$ to $\binom{n}{k}$ is either

(i) a path from $\binom{0}{0}$ to $\binom{n-1}{k}$ followed by one vertical move $(a)$, or 

(ii) a path from $\binom{0}{0}$ to $\binom{n-1}{k-1}$ followed by one diagonal move $(b)$.

So, the total number of paths 
is $path(n,k) = path(n-1,k)+path(n-1,k-1)$.
The numbers $path(n,k)$
are computed in exactly the same way as the binomial coefficients
$\binom{n}{k}$ starting with the same initial values.  Hence it
follows that for all integers n and k with $0 \leq k \leq n$, \[
path(n,k) = \binom{n}{k}\] Thus the value of an entry $\binom{n}{k}$ of
Pascal's triangle represents the number of paths from the top left
corner to that entry using only moves of types $(a)$ and $(b)$.  And, we
have derived another combinatorial interpretation of the numbers $\binom{n}{k}$.  }

%\problem 
%Patrick's baseball card collection consists of 2 Roger Clemens rookie cards, 5
%Pedro Martinez rookie cards and 4 Ken Griffey Jr. rookie cards.  In addition to
%these cards, he has 20 different cards of players he does not care about.  
%(mostly Yankees, of course)  To him these cards are indistinguishable.  He also
%cannot distinguish between same-player rookie cards.

%Patrick would like to arrange his baseball cards in a baseball card box which
%contains 4 distinguishable rows.

%\bparts
%\ppart
%How many ways are there for Patrick to arrange all his cards on a single 
%given row?

%\solution{  
%$\frac{31!}{2!\cdot 5!\cdot 4!\cdot 20!}$}
%
%%\ppart 
%%In how many ways can he arrange the baseball cards in the whole box if
%%order within a specific row did not matter?  (i.e.  each row is a bin)
%%
%%\solution{
%%$\binom{5}{3}\cdot\binom{8}{3}\cdot\binom{7}{3}\cdot\binom{23}{3}$  
%%}
%%
%%\ppart Same question as part b), when order matters.
%
%\ppart 
%In how many ways can he arrange the baseball cards in the whole box?  
%
%\solution{
%The arrangement of the cards in the box in different rows 
%correspond to arranging the cards plus 3 "dividers" ( seperating
%one row from the next), so that some cards appear before the first
%dividor, some after etc... This amounts to 
%$\frac{34!}{2!\cdot 5! \cdot 4! \cdot 20! \cdot 3!}$
%}
%\eparts


\problem \textbf{Binomial Coefficients.  The Binomial Theorem.}

\bparts

\ppart Define a \textit{composition} of $x$ as an
\textit{ordered} sum of positive integers that equal $x$.  I.e., the
compositions of $4$ are

\begin{center}
\begin{tabular}{ll}
$1+1+1+1$ & $3+1$ \\
$2+1+1$ & $1+3$ \\
$1+2+1$ & $2+2$ \\
$1+1+2$ & $4$ \\
\end{tabular}
\end{center}

For any $n$, count the number of compositions of $n$.

\solution{We can use a dot/bar diagram to conceptualize this.  Note
that a composition of $x$ can be viewed as a way to place bars between
$x$ dots; for example, for $x=4$:

\begin{center}
\begin{tabular}{lc}
$1+1+1+1$ & $\cdot|\cdot|\cdot|\cdot$ \\
$2+1+1$ & $\cdot\ \cdot|\cdot|\cdot$ \\
$1+3$ & $\cdot|\cdot\ \cdot\ \ \cdot$ \\
\end{tabular}
\end{center}

Thus, there are $2^{n-1}$ such compositions.}

\ppart Define a $k$-\textit{composition} of $x$ as a composition of
$x$ with exactly $k$ elements.  Count the number of $k$-compositions
of $n$.  Use part (a) and your answer
to derive \[ \sum_{i=0}^{m} \binom{m}{i} = 2^m \]

\solution{Using the dot/bar diagram from the previous part, it is
clear that you are choosing $k-1$ positions to place bars out of $n-1$
possible positions.  This is $\binom{n-1}{k-1}$.

Since the set of $k$-compositions is disjoint from the set of $j$
compositions for $k\not=j$, we can simply add them up: 
\[ \sum_{k=1}^{n} \binom{n-1}{k-1} = 2^{n-1} \]  

Cleaning this up by setting $m:=n-1$ and $i:=k-1$, we have 
\[ \sum_{i=0}^{m} {\binom{m}{i}} = 2^m \]

}

\ppart Give a combinatorial proof\footnote{Recall examples of
combinatorial proofs from lecture} for 
$$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} {\binom{n}{2k}} = 2^{n-1} $$

\solution{The above sum corresponds to how many ways
are there to choose an even number of
elements from $n$ elements.

Think of the selection process as follows:
for each element $x_1$, $x_2, \ldots, x_{n-1}$ we have two 
choices of whether we select it or not, and 
when we get to $x_n$, we have only 1 choice.  Namely,
if thus far we have chosen an
even number of the elements $x_1$, $x_2, \ldots, x_{n-1}$, we must
leave $x_n$ out; if we have chosen an odd number of the elements $x_1$,
$x_2, \ldots, x_{n-1}$, we must put $x_n$ in.  Hence the number of
combinations of S with an even number of elements equals $2^{n-1}$. }

\ppart Use the previous part to conclude that 
\[\sum_{k=0}^{n} {(-1)^k \binom{n}{k}} = 0 \]

\solution
{
Notice that 
\[\sum_{k=0}^{\lfloor{ \frac{n-1}{2} \rfloor}} \binom{n}{2k+1} \]
is the number of ways to choose an odd number of elements from
$n$. Thus, by the same reasoning above, it is also equal to $2^{n-1}$.
Subtracting the number of ways to choose an even number of
elements from the number of ways to choose an odd number of elements
we get 0.

Written differently, 
\[\sum_{k=0}^{\lfloor n/2\rfloor} \binom{n}{2k}   - 
\sum_{k=0}^{\lfloor{ \frac{n-1}{2} \rfloor}} \binom{n}{2k+1} = \]
\[\sum_{k=0}^{n} (-1)^k \binom{n}{k} = 0 \]  
}

\eparts


\problem
You are at point $(0,0,0)$ in three-dimensional space, and you need to get to 
point $(i,j,k)$. You can only make unit-length moves parallel
to three coordinate axes, and only moves that get you closer to
your goal. How many different paths can you take?

\solution{
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$
steps.  Of these steps, $i$ must be along one dimension, $j$ must be
along another, and $k$ must be along the third.  The question becomes
how to distribute the three types of steps amongst the $i+j+k$ total
steps.  There are $\binom{i+j+k}{i}$ ways to choose which of the
$i+j+k$ steps will be along the first dimension, $\binom{j+k}{j}$
ways to choose which of the $j+k$ remaining steps will be along the
second dimension, and ${\binom{k}{k}} = 1$ way to choose which of the
$k$ remaining steps will be along the third dimension.  By the product
rule, the total number of different paths is ${\binom{i+j+k}{i}}
{\binom{j+k}{j}}$.

Alternatively, you could argue as follows:
No matter how you arrive at $(i,j,k)$, you must have taken $i+j+k$ steps.  Of
these steps, $i$ must be along one dimension, $j$ must be along
another, and $k$
must be along a third.  The question becomes how to arrange these steps in
order.  This can be done in $\binom{i+j+k}{i, j, k}$ ways.  (Consult the 
multinomial definition for the factorial form of this.)
}

\end{problems}

\newpage

\section*{Topics for Week of November 8th, 1999}

\subsection*{Combinations\\
Rosen 4.3, Tutorial Notes 10/24, Fall 97}
\begin{itemize}
\item
Counting Combinations
\item
Binomial Coefficents
\item
Pascal's Triangle
\item
The Binomial Theorem
\end{itemize}

\subsection*{$r$-Combinations\\
F97 Lec Notes 15 }

\begin{itemize}
\item
The division Rule 
\item
Examples of $r$-Combinations
\end{itemize}

\subsection*{Counting with Repetitions \\
F97 Lec Notes 16, Rosen 4.6 }
\begin{itemize}
\item
Counting Combinations and $r$-combinations with Repetitions
\item 
Examples of the Use of Combination with Repetitins:
data compression, stars and balls
\item
$r$-combinations with at least one item of each kind
\item
$r$-combinations with limited Repetitions
\item
Counting Permutations and $r$-Permutations  with Repetitions
\item
Counting Permutations with Limited Repetitins 
\item
Multinomial Coeficients 
\item
Permutations of Sets with Indistinguishable Objects
\end{itemize}

\end{document}
\problem

[Multinomials]
Consider the following identity 

$$\binom{a+b+c+d}{a,b} *  \binom{c+d}{d} =$$

$$\binom{a+b+c+d}{d}  * \binom{a+b+c}{ a} * \binom{b+c}{b,c}$$
\bparts
\ppart 
Prove this identity using algebraic manipulation.

\solution{
First, note that the left hand side $$LHS =\frac{ (a+b+c+d)! \cdot (c+d)!}{ a! b! (c+d)! c! d! } 
= \frac{(a+b+c+d)!}{a! b! c! d!}$$

Now, the right hand side 
$$RHS = \frac{(a+b+c+d)! \cdot (a+b+c)! \cdot (b+c)!}{d! (a+b+c)! a! (b+c)! b! c!} 
= LHS$$
}

\ppart
Prove this identity via a combinatorial argument.

\solution {

Both sides represent splitting up a set of size a+b+c+d in
4 subsets of size a, b, c and d respectively.

For LHS we first chooose the subsets of size a and b.  Then
from the remaining c+d elements we choose d, having c left
over for the last subset.

For RHS we first choose a subset of size d first, then a 
subset of size a, and finally divide up the remaining b+c 
into two sets of size b and c.

}
\eparts
