\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

%% TUTORIAL 9: Permutations/Combinations w/ w/o repetitions

\ifshowsolutions
  \tutsol{9}{November 1, 2001}{\stamp}
\else
  \tutprobn{9}{November 1, 2001}{\stamp}
\fi

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem4 spring98, from M&R, # 4.7.5

\problem How many ways can 4 balls be placed in 4 urns if \dots
\begin{problemparts}
\problempart both the balls and the urns are distinguishable.

\solnospace{$4\cdot 4\cdot 4\cdot 4 =256$.}

\problempart neither the balls nor the urns are distinguishable.

\solnospace{5.  This is the number of ways to partition a multiset
$\{1,1,1,1\}$ of 4 indistinguishable objects into 4 (possibly empty)
subsets.  We can either put $\{1,1,1,1,\}, \emptyset, \emptyset,
\emptyset$ or $\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or $\{1,1\},
\{1,1\},\emptyset,\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.}

\problempart the balls are distinguishable but the urns are not.

\solnospace{15.  We can put either all 4 balls in one urn; or 3 in one, 1
in another; or 2 in one, 2 in another; or 2 in one, 1 in one and 1 in
another; or 1 ball in each urn.  The balls are distinguishable, so there
are $\dbinom{4}{3}$ ways of putting 3 in one urn.  There are $\dbinom{4}{2}$
ways of putting 2 in one and 1 in each of the other two.  There are
$\binom{4}{2}/2$ ways of putting 2 in one and 2 in another. Since the urns
are indistinguishable, the case where all the balls are placed in the same
urn and the case where each ball is places in a different urn are unique.
So the total number of ways is
\[
1 + \binom{4}{3} + \frac{1}{2}\binom{4}{2} + \binom{4}{2} + 1 = 15.
\]
}

\problempart the urns are distinguishable but the balls are not.

\solnospace{35.  This is a stars and bars problem with the balls being
stars and the urns bars.  The answer is $\dbinom{4+4-1}{4} = \dbinom{7}{4}
= 35$.}

\end{problemparts}


%Fall 99 Final exam Prob 10, spring00 ps7-5, spring96 ps7
%revised by ARM 10/25/01
% topic: combinatorics, algebraic manipulation

\problem You want to choose a team of $m$ people from a pool of $n$ people
for your startup company, and from these $m$ people you want to choose $k$
to be the team managers.  You took 6.042, so you know you can do this in
\[
\binom{n}{m}\binom{m}{k}
\]
ways.  But your CFO, who went to Harvard Business School, comes up with
the formula
\[
\binom{n}{k}\binom{n-k}{m-k}.
\]
Before you dump on your CFO or Harvard Business School, you decide to
check his answer against yours---fortunately.

\bparts

\ppart Give an algebraic proof that your CFO's formula agrees with yours.

\solnospace{
\begin{eqnarray*}
\binom{n}{m}\binom{m}{k}
& = & \frac{n!}{m! (n-m)!} \frac{m!}{k! (m-k)!} \\
& = & \frac{n!}{(n-m)! k! (m-k)!} \\
& = & \frac{n! (n-k)!}{(n-m)! k! (m-k)! (n-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{(n-m)!(m-k)!} \\
& = & \frac{n!}{k! (n-k)!} \frac{(n-k)!}{((n-k) - (m-k))! (m-k)!} \\
& = & \binom{n}{k}\binom{n-k}{m - k}.
\end{eqnarray*} 
}

\ppart Now give what the Notes call a \emph{combinatorial argument}
proving this same fact.

\solnospace{Instead of choosing first $m$ from $n$ and then $k$ from $m$,
you could alternately choose the $k$ managers from the $n$ people and then
choose $m-k$ people to fill out the team from the remaining $n-k$ people.
This gives you $\dbinom{n}{k} \dbinom{n-k}{m-k}$ ways of picking your
team.  Since you must have the same number of options regardless of the
order in which you choose to pick team members and managers,
\[
\binom{n}{m} \binom{m}{k} = \binom{n}{k} \binom{n-k}{m-k}.
\]
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset7 problem8 spring98, exercise $4.6-42$ of Rosen.
\problem

A shelf holds 13 books in a row.  How many ways are there to choose 
five books so that no two adjacent books are chosen?

\solnospace{
There are 5 bars (chosen books), and therefore there are
6 places where the 8 stars (non-chosen books) can fit (before the first 
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one star 
in it, so that adjacent books are not chosen. Once we have placed these
4 stars, there are 4 stars left to be placed in 6 slots. The number of
ways to do this is therefore
\[
\binom{6+4-1}{4}=\binom{9}{4}=126.
\]
}

\problem  By now you have probably seen the identity
\begin{equation}\label{binminus}
\sum_{i=0}^n (-1)^i \binom{n}{i} = 0
\end{equation}
more than once.
\bparts

\ppart This identity is an immediate consequence of the Binomial Theorem.
Explain how.

\solnospace{We know the
\begin{equation}\tag{Binomial Theorem}
(x + y)^n = \sum_{i=0}^n \binom{n}{i}x^iy^{n-i}.
\end{equation}
So let $x = -1$ and $y=1$ to obtain equation~(\ref{binminus}).
}

\ppart Conclude from equation~(\ref{binminus}) that $\set{1,2,\dots, n}$ has
an equal number of odd- and even-size subsets.

\solnospace{The number of odd-size subsets is the number of subsets of size $1, 3,
\dots, 2i+1, \dots$ namely
\[
\binom{n}{1} + \binom{n}{3} + \cdots + \binom{n}{2i+1} + \cdots
\]
which we can write as
\begin{equation}\label{oddterms}
\sum_{i=1}^{\ceil{n/2}} \binom{n}{2i-1}.
\end{equation}
But this is exactly the absolute value of the sum of the negative-valued
terms on the LHS of equation~(\ref{binminus}).

Likewise, the number of even-size subsets is the number of subsets of size
$0, 2, \dots, 2i, \dots$ namely
\[
\binom{n}{0} + \binom{n}{2} + \cdots + \binom{n}{2i} + \cdots
\]
which we can write as
\begin{equation}\label{eventerms}
\sum_{i=0}^{\floor{n/2}} \binom{n}{2i}.
\end{equation}
But this is exactly the sum of the nonnegative-valued terms on the LHS of
equation~(\ref{binminus}).

So the LHS of equation~(\ref{binminus}) also equals
expression~(\ref{eventerms}) minus expression~(\ref{oddterms}).  Hence,
the values of the expressions~(\ref{oddterms}) and~(\ref{eventerms}) are
the same.}

\ppart Conversely, equation~(\ref{binminus}) will follow if we show that
there is an equal number of even- and odd-size subsets of
$\set{1,2,\dots,n}$ whenever $n>0$.  Prove that there are an equal number
by defining a simple bijection between the even-size and odd-size subsets
of $\set{1,2,\dots,n}$.

\solnospace{
An elegant bijection is 
\[
g(S) \eqdef \begin{cases}
            S-\set{n} & \text{if } n \in S\\
            S \union \set{n} & \text{otherwise}.
            \end{cases}
\]

Another approach is based on the fact that if $n$ is odd, then a subset
has odd size iff its complement is even size, and vice-versa.  So if $n$
is odd, the letting any subset $S \subseteq \set{1,2,\dots,n}$ map to its
complement $\bar{S} \eqdef \set{1,2,\dots,n} - S$ is a bijection between
the even- and odd-sized subsets.

To extend this idea to the case when $n$ is even, we observe that $n-1$ is
odd, so we use the bijection, $f$, we have from the even-size subsets of
$\set{1,2,\dots,n-1}$ to the odd-sized ones.  We can extend this bijection
to the remaining even-size subsets of $\set{1,2,\dots,n}$, namely the ones
that contain $n$.  To do this, map $S \union \set{n}$, where $S$ is an
even-size subset of $\set{1,2,\dots,n-1}$, to the set $f(S) \union
\set{n}$.}


\end{problemparts}

\iffalse

\problem Prove the following identities both by algebraic manipulation and
by giving a combinatorial argument:
\begin{problemparts}
\problempart \[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\]
\problempart \[\binom{2n}{2} = 2\binom{n}{2} + n^2\]
\problempart \[ \sum_{k=0}^n 2^k \binom{n}{k} = 3^n\]
\end{problemparts}

\fi

\iffalse

% source: spring00 ps7-5
% source: fall94 ps7
% topic: combinatorics, binomial theorem
\problem We wish to prove the identity
\[\sum_{r=0}^n\binom{n}{r}^2 = \binom{2n}{n}\ ,\]
for $n\in\naturals$.

\begin{problemparts}
\problempart Use the binomial theorem and the fact that
\[(1+x)^n(1+x^{-1})^n = x^{-n}(1+x)^{2n}\] to prove the identity.

\solnospace{
We know that:	
\begin{eqnarray*}
(1+x)^n (1+x^{-1})^n	&=& x^{-n}(1+x)^n x^n (1+x^{-1})^n \\
			&=& x^{-n}(1+x)^n (x+1)^n \\
			&=& x^{-n}(1+x)^{2n}\\
\end{eqnarray*}
which proves the equality of the two expressions. \\
Using the binomial theorem:
\begin{eqnarray*}
\sum_{i=0}^n \binom{n}{i}x^i \sum_{j=0}^n \binom{n}{j}x^{-j} &=& x^{-n}\sum_{i=0}^{2n} \binom{2n}{i}x^i\\
\end{eqnarray*}
Then equating the coefficients of $x^0$:
\begin{eqnarray*}
\sum_{i=0}^n \binom{n}{i}^2 &=& \binom{2n}{n}
\end{eqnarray*}
}

\iftrue

\problempart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Use the fact that \[\binom{n}{r}^2 = \binom{n}{
r}\binom{n}{n-r}\] to give a combinatorial proof of the identity.

\else

\problempart Notice that \[\binom{n}{r}^2 = \binom{n}{r}\binom{n}{n-r}\]
so that the identity to prove is no else than
\[\sum_{r=0}^n\binom{n}{r}\binom{n}{n-r} = \binom{2n}{n}\]
Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue to give a combinatorial proof of the identity.

\fi

\solnospace{
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
$$\binom{n}{r} \binom{n}{n-r} = \binom{n}{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 \binom{n}{r}^2.$$  But there are  $\dbinom{2n}{n}$ ways to
choose $n$ objects, so these must be the same number.
}
\end{problemparts}
\fi

\end{problems}

\end{document}
