\include{preamble}
\setcounter{try}{21}
\renewcommand{\thefootnote}{\fnsymbol{footnote}}
\title{}
\author{Zajj Daugherty}
\date{\today}
\usepackage{multicol}
\begin{document}
\begin{flushright}
SOLUTIONS\\
Homework 5\\
Due 3/6/19
\end{flushright}
%-----------------% HANDOUT 8 %-----------------%
\begin{try}~
\begin{enumerate}[(a)]
\item Consider the set $\{a,b,c\}$. For each of the following, (A) list the objects described, (B) give a formula that tells you how many you should have listed, and (C) verify that the formula and the list agree.
\begin{enumerate}[(i)]
\item Permutations of $\{a,b,c\}$.
\begin{ans}
\begin{enumerate}[(A)]
\item $abc, acb, bac, bca, cab, cba$
\item $P(3,3) = 3!$
\item $3!=6$, and there are 6 items in (A).
\end{enumerate}
\end{ans}
\item Two-permutations of $\{a,b,c\}$.
\begin{ans}
\begin{enumerate}[(A)]
\item $ab, ac, ba, bc, ca, cb$
\item $P(3,2) = 3*2$
\item $3*2 = 6$, and there are 6 items in (A).
\end{enumerate}
\end{ans}
\item Size-two subsets of $\{a,b,c\}$.
\begin{ans}
\begin{enumerate}[(A)]
\item $\{a,b\}, \{a,c\}, \{b,c\}$
\item $\binom{3}{2} = 3*2/2!$
\item $3*2/2!=3$, and there are 3 items in (A).
\end{enumerate}
\end{ans}
\end{enumerate}
\item For each of the following, classify the problem as a permutation or a combination problem or neither, and give an answer using an unsimplified formula. (Answers should look, for example, like $5*4$ or $5!/2!$ instead of $P(5,4)$ or $20$.)
\begin{enumerate}[(i)]
\item In how many different orders can five runners finish a race if no ties are allowed?
\begin{ans}
This is a ``permutation'' problem, and there are \fbox{$5! = 5*4*3*2*1$} ways.
\end{ans}
\item How many strings of 1's and 0's of length seven have exactly three 1's?
\begin{ans}
This is a ``combination'' problem: Choosing the places where the 1's go gives $\binom73 = \fbox{$\frac{7!}{4!3!}$}$ strings.
\end{ans}
\item How many strings of 1's and 0's of length seven have three or fewer 1's?
\begin{ans}
This is a ``combination'' problem, to be computed in cases depending on \emph{exactly} how many 1's the sequence has:
$$\binom73 + \binom72+\binom71+\binom70 = \fbox{$\displaystyle 7!\left(\frac{1}{4!3!}+\frac{1}{5!2!}+\frac{1}{6!1!}+\frac{1}{7!0!}\right)$}.$$
\end{ans}
\item How many three-digit numbers are there with no 1's? (a three-digit number is something like 144 or 009 or 053)
\begin{ans}
This is neither combination nor permutation. This is just product rule: there are nine choices for each digit, giving \fbox{$9^3$} in total.
\end{ans}
\item How many three-digit numbers are there with no digits repeated?
\begin{ans}
This is a ``permutation'' problem, and there are $P(10,3) = \fbox{$10*9*8$}$ of these.
\end{ans}
\end{enumerate}
\smallskip
\item For each of the following, provide your answers in an unsimplified form, and justify.
\begin{enumerate}[(i)]
\item A six-sided dice is rolled 5 times. How many ways could it turn out that a value greater than 4 (i.e.\ 5 or 6) is rolled exactly twice? \emph{(Hint: first pick which rolls are from $\{5,6\}$ (this implies which rolls are from $\{1,2,3,4\}$ for free), and then pick the values for the $\{5,6\}$-valued rolls, and finally pick the values for the other rolls (the $\{1,2,3,4\}$-valued rolls).)}
\begin{ans}
First choose when the high rolls happen: $\binom{5}{2} = \frac{5*4}{2}$ possibilities.\\
Then choose how the high rolls go: $2*2$ possibilities. \\
Then choose how the low rolls go: $4*4*4*4$ possibilities. \\
(For example, a roll sequence like $5,2,2,6,1$ is in the category of
\begin{enumerate}[\qquad\qquad]
\item[]roll sequence goes HLLHL;
\item[]high rolls go $5$ then $6$;
\item[]low rolls go $2$ then $2$ then $1$.)
\end{enumerate}
Now use product rule to combine: $ \frac{5*4}{2}(2*2)(4*4*4*4)$.
\end{ans}
\item If 10 men and 10 women show up for one team of an intramural basketball game, how many ways can you pick 5 people to play for one team if there must be at least one person of each gender on the team?
\begin{ans}
Break this into the cases of how the gender balance works: 4 men and 1 women, 3 men and 2 women, 2 men and 3 women, or 1 man and 4 women. Then use product rule in each of those cases to get
\begin{align*}\binom{10}{4}\binom{10}{1} &+ \binom{10}{3}\binom{10}{2}
+\binom{10}{2}\binom{10}{3} + \binom{10}{1}\binom{10}{4}\\
&= \left(\frac{10!}{4!1!}\right)^2+\left(\frac{10!}{3!2!}\right)^2+\left(\frac{10!}{3!2!}\right)^2 + \left(\frac{10!}{4!1!}\right)^2
\end{align*}
\end{ans}
\item How many ways are there for 5 women and 2 men to stand in line? Now how many ways are there for them to stand in line if the two men don't stand next to each other? (The men and the women are distinct individuals.)
\begin{ans}
\begin{enumerate}[]
\item Ways are there for 5 women and 2 men to stand in line:\\
This is just 7 people standing in line, which has $7!$ possibilities. \medskip
\item If the two men don't stand next to each other:\\
Pick where then men are standing, of which there are $\binom72 - 6$ possibilities.\\
Then pick the order of the women -- $5!$ -- and the order of the men -- $2$.\\
Combine using product rule: $(\binom72 - 6)5!*2$.
\end{enumerate}
\end{ans}
\end{enumerate}
\item For each of the following identities, (A) explain in words why it makes sense given what it represents, and then (B) verify it algebraically using the formulas for permutation or combination.
\\
\emph{(For example, an answer for (A) might start out looking like ``$P(n,1)$ means\dots'', and an answer for part (B) should look like a calculation that starts with ``$P(n,1) = \dots$''.)}
\begin{enumerate}[(i)]
\item $P(n,1) = n$
\begin{ans}
\begin{enumerate}[(A)]
\item This is the number of ways to pick one thing out of $n$, of which there are $n$ possibilities. Order doesn't come in to play, since there's only one thing.
\item $P(n,1) = \frac{n!}{(n-1)!} = n$
\end{enumerate}
\end{ans}
\item $P(n,0) = 1$
\begin{ans}
\begin{enumerate}[(A)]
\item This is the number of ways to pick nothing out of $n$, of which there is only one possibility.
\item $P(n,0) = \frac{n!}{n!} = 1$
\end{enumerate}
\end{ans}
\item $P(n,k+1) = P(n,k)*(n-k)$
\begin{ans}
\begin{enumerate}[(A)]
\item $P(n,k+1) $ is the number of ways to choose $k+1$ things from $n$ in order. Since it's in order, you can choose the first $k$ things first, and then choose the last thing separately. After $k$ things, there are $n-k$ to choose from.
\item$P(n,k+1) = \frac{n!}{(n-(k+1))!} = \frac{n!}{(n-k)!/(n-k)}P(n,k)*(n-k)$
\end{enumerate}
\end{ans}
\item $\binom{n}{1} = n$
\begin{ans}
\begin{enumerate}[(A)]
\item This is the number of ways to pick one thing out of $n$, of which there are $n$ possibilities.
\item $\binom{n}{1} = \frac{n!}{(n-1)!1!} = n$
\end{enumerate}
\end{ans}
\item $\binom{n}{n} = 1$
\begin{ans}
\begin{enumerate}[(A)]
\item This is the number of ways to choose everything all at once out of a group of $n$. There is one way to do this -- pick everything.
\item $\binom{n}{n} = \frac{n!}{(n-n)!n!} = 1$ (since $0! = 1$)
\end{enumerate}
\end{ans}
\item $\binom{n}{0} = 1$
\begin{ans}
\begin{enumerate}[(A)]
\item This is the number of ways to choose nothing from $n$ things. There is one way to do that - don't take anything.
\item $\binom{n}{0} = \frac{n!}{(n-0)!0!}=1$ (again, since $0! = 1$)
\end{enumerate}
\end{ans}
\item $\binom{n}{k} = \binom{n}{n-k}$
\begin{ans}
\begin{enumerate}[(A)]
\item This is because choosing $k$ things from $n$ is the same as picking $n-k$ things from $n$ to exclude.
\item
$\binom{n}{k} = \frac{n!}{(n-k)!k!}= \frac{n!}{k!(n-k)!}= \binom{n}{n-k}$
\end{enumerate}
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
\begin{try} For each of the following, be sure to include how the pigeonhole principle or its generalized version apply in your justifications, or why neither of them do.
\begin{enumerate}[(1)]
\item The lights have gone out and you're digging through an unorganized sock drawer filled with unmatched black socks and brown socks (otherwise roughly identical).
\begin{enumerate}
\item If you're pulling them out at random, how many socks do you need to take out to ensure you have a matching pair if there are 10 of each kind of sock? How about if there are 20 of each? 100 of each?
\begin{ans}
It doesn't matter how many socks you have to choose from as long as you have enough to apply generalized pigeonhole principle. In any case, the colors are the boxes and the socks you've picked are the items, and so you want to solve $\lceil n/2 \rceil \geq 2$ for the minimal $n$: $n=3$.
\end{ans}
\item Again pulling at random, how many socks do you need to take out to ensure you have a matching brown pair if there are 10 of each kind of sock? How about if there are 20 of each? 100 of each?
\begin{ans}
This is not pigeonhole principle since you need brown in particular. This is asking to guarantee that a \emph{specific} box has at least 2 object. So you need to take into account that you might pull out all of the black socks before you get a single brown sock. Therefore you need to pick 12 if there are 10 of each kind of sock, 22 if there are 20 of each, and 102 if there are 100 of each.
\end{ans}
\end{enumerate}
\item Explain why, out of any set of four integers, at least two have the same remainder when divided by 3.
\begin{ans}
Here the elements are the integers and the remainders are the boxes. There are only three possible remainders when dividing by 3: 0, 1, and 2. Since you've picked 4 objects, the pigeonhole principle tells us at least 2 of them go in the same box, i.e.\ that 2 of them have the same remainder.
\end{ans}
\item A recent estimate showed that the US and Canada together (which share the country code $+$1) have approximately 134,000,000 phone lines in use. What is the minimum number of area codes needed to make that possible?
\begin{ans}
The boxes are the area codes and the 7-digit phone numbers are the objects. You have to ensure that there are enough of them so that no more than then number of possible 7-digit phone numbers are forced into the same area code. Since there are $8*10^6$ possible 7-digit phone numbers, you want to solve for the minimal $k$ such that
$$\lceil(134*10^6) /k \rceil \leq 7*10^6.$$
This is $k=20$.
\end{ans}
\item Let $f: A \to B$ be a function between finite sets such that $|A| > |B|$. Explain why $f$ cannot possibly be injective. (Consider the sizes of the preimages $\{f^{-1}(b) ~|~ b \in B\}$.)
\begin{ans}
Here, the elements of $B$ are the boxes and the elements of $A$ are the objects. A function $f$ is an assignment of what objects go into what boxes (an object $a$ is in box $b$ if $a$ is in the preimage of $b$, i.e.\ $f(a) = b$). Since there are more objects than boxes, pigeonhole principle tells us that some box has more than one object in it, i.e.\ some element of $b$ has more than one element of $a$ in its preimage. Therefore the function is not injective.
\end{ans}
\item Explain why, in any sequence of $n$ consecutive integers, at least one of them must be divisible by $n$. (Start with, say, $n=4$ as an example.)
\begin{ans}
Like in part (c), the remainders are the boxes and the consecutive integers are the boxes.
Let $a, a+1, a+2, \dots, a+n-1$ be a collection of consecutive ingeters. And suppose the least of these integers has remainder $r$ when divided by $n$ (so that $a = kn+r$, with $0\leq r 0\\ 1 & \text{if } k=0.\end{cases}
$$
For example,
$$\binom{0.2}{3} = \frac{0.2(-0.8)(-1.8)}{3*2*1}.$$
\begin{enumerate}[(i)]
\item Compute $\binom{\pi}{4}$, $\binom{1/2}{2}$, and $\binom{7/3}{0}$.
\begin{ans}
We have
\begin{align*}
\binom{\pi}{4}&= \pi(\pi-1)(\pi-2)(\pi-3)/4! \approx 4.045;\\
\binom{1/2}{2}&=(1/2)(1/2-1)/2! = -1/8; \text{ and}\\
\binom{7/3}{0} &= 1, \text{ by definition, since $k=0$ here}.
\end{align*}
\end{ans}
\item Verify algebraically that if $n$ is a positive integer and $0 \le k \le n$, then
$$\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}.$$
Check this identity for $n=5$ and $k=3$ (you should probably do this first).
\begin{proof}
For $k = 0$, then both sides are equal to 1. Otherwise, we have
\begin{align*}
\binom{-n}{k} &= \frac{(-n)(-n-1)(-n-2) \cdots (-n-k+1)}{k!}\\
&= (-1)^k \frac{n(n+1)(n+2) \cdots (n+k-1)}{k!}\\
&= (-1)^k \frac{X(X - 1)(X - 2) \cdots
\big(X - k + 1\big)}{k!},\\
&\hspace{1in}
\text{where $X = n+k-1$, flipping the order of multiplication,}\\
&\hspace{1in}\text{in particular, since } X - k+1 = (n+k-1) - k + 1 = n,\\
&= (-1)^k\binom{n+k-1}{k},
\end{align*}
as desired.
\end{proof}
\item BONUS: The \emph{extended binomial theorem} states that for any real number $u$, we have
$$(1+x)^{u} = \sum_{i=0}^\infty \binom{u}{k} x^k.$$
Now recall from calculus the Taylor series expansion
$$(1+x)^{-1} = \sum_{i=0}^\infty x^i(-1)^i.$$
Check that the first 3 terms ($i=0,1,2$) of our known Taylor series expansion match the first 3 terms of the extended binomial theorem expansion (when $u = -1$). Finally, verify that this example matches correctly for all terms by showing that $\binom{-1}{k} = (-1)^k$ for any $k \in \ZZ_{\ge0}$.
\begin{proof}
Note that
\begin{align*}
\binom{-1}{k} &= \frac{-1(-1-1)(-1-2) \cdots (-1-k+1)}{k!} \\
&= \frac{-1(-2)(-3) \cdots (-k)}{k!} \\
&= \frac{(-1)^k k!}{k!} = (-1)^k.
\end{align*}
So the extended binomial theorem says that
$$(1+x)^{-1} = \sum_{i=0}^\infty \binom{-1}{k} x^k = \sum_{i=0}^\infty (-1)^kx^k,$$
as desired.
\end{proof}
\item BONUS: Show in that the Taylor series expansion for $(1+x)^{-n}$ matches the extended binomial theorem for $n=3$.
\begin{proof}
We have \begin{align*}
\binom{-3}{k} &= \frac{-3(-3-1)(-3-2) \cdots (-3-k+1)}{k!} \\
&= \frac{-3(-4)(-5) \cdots (-k)(-(k+1))(-(k+2))}{k!} \\
&= \frac{(-1)(-2)(-3)(-4)(-5) \cdots (-k)(-(k+1))(-(k+2))}{(-1)(-2)k!} \\
&= \frac{(-1)^{k+2} k! (k+1)(k+2)}{2(k!)} \\
&= (-1)^{k+2}\frac{(k+1)(k+2)}{2} \\
&= (-1)^{k}\frac{(k+1)(k+2)}{2}.
\end{align*}
So the extended binomial theorem says that
$$(1+x)^{-3} = \sum_{i=0}^\infty \binom{-3}{k} x^k = \sum_{i=0}^\infty (-1)^{k}\frac{(k+1)(k+2)}{2}x^k
= \sum_{i=0}^\infty \frac{(k+1)(k+2)}{2}(-x)^k.$$
On the other hand, we have
\begin{align*}
\frac{d}{dx}(1+x)^{-1} &= -(1+x)^-2; \quad \text{so that}\\
\frac{d^2}{dx^2}(1+x)^{-1} &= \frac{d}{dx}\left(-(1+x)^-2\right) = 2(1+x)^{-3}.
\end{align*}
Thus
\begin{align*}
(1+x)^{-3} &= \frac{1}{2}\frac{d^2}{dx^2}(1+x)^{-1}\\
&= \frac{1}{2}\frac{d^2}{dx^2}\left(\sum_{k=0}^{\infty}(-1)^kx^k\right)\\
&= \frac{1}{2}\sum_{k=0}^{\infty}(-1)^k\left(\frac{d^2}{dx^2}x^k\right)\\
&= \frac{1}{2}\sum_{k=2}^{\infty}(-1)^k\left(k(k-1)x^{k-2}\right)\\
&= \frac{1}{2}\sum_{k=0}^{\infty}(-1)^k (k+2)(k+1)x^{k}\\
&= \frac{1}{2}\sum_{k=0}^{\infty} \frac{(k+1)(k+2)}{2}(-x)^k,
\end{align*}
which matches what we got from the extended binomial theorem.
\end{proof}
\end{enumerate}
\end{enumerate}
\end{try}
\pagebreak
\begin{try}~
\begin{enumerate}[(a)]
\item Explain the example provided for the proof of Vandermonde's in the notes using words.
\begin{ans}
In proving Vandermonde's identity, we showed that you can count the size $r$ subsets of $A \sqcup B$ in two ways, where $|A| = n$, $|B| =m$, and $r \leq n,m$. The first way was to count them all at once. In this example, when $r=3$, these are
the subsets listed in the table.
The second way to count them is take size $k$ subsets of $A$ and size $r-k$ subsets of $B$ and union them. These correspond to the different columns of the table (the first column is taking no elements from $B$, the second column is taking one element from $B$, and so on.
\end{ans}
\item Substitute $m = r = n$ into Vandermonde's identity to show that
$$\binom{2n}{n} = \sum_{k=0}^n \binom{n}{k}^2,$$
and check this identity for $n = 2$.
\begin{ans}
We have
\begin{align*}
\binom{n+m}{r}\Big|_{m = r = n} &= \binom{2n}{n}\\
&= \sum_{j=0}^r \binom{m}{j} \binom{n}{r-j} \Big|_{m = r = n}\\
&= \sum_{j=0}^n \binom{n}{j} \binom{n}{n-j}
= \sum_{j=0}^n \binom{n}{j}^2.
\end{align*}
For $n=2$, we get
\begin{align*}
\binom{2*2}{2} &= \binom{4}{2} = 6\\
= \sum_{j=0}^2 \binom{2}{j}^2&= \binom{2}{0}^2+\binom{2}{1}^2+\binom{2}{2}^2\\
&= 1^2 + 2^2 + 1^2 = 6. \quad \checkmark
\end{align*}
\end{ans}
\item Consider the identity
$$\binom{n}{k} k = \binom{n-1}{k-1} n$$
for integers $1 \leq k \leq n$.
\begin{enumerate}[(i)]
\item Verify this identity for $n = 5$ and $k = 3$.
\begin{ans}
We have
\begin{align*}
\binom{5}{3} 3 &= 10*3=30\\
&=\binom{5-1}{3-1} 5 = \binom{4}{2}5 = 6*5 = 30. \qquad \checkmark
\end{align*}
\end{ans}
\item Explain why this identity is true using a combinatorial argument.\\
{[}\emph{Hint: Count, in two different ways, the number of ways to pick a subset with $k$ elements from a set with $n$ elements, along with a distinguished element of that $k$-element subset. For example, out of $n$ people, pick a committee of $k$ people and choose someone on that committee to organize their meetings.
}{]}
\begin{ans}
We can count the number of ways to choose a committee of $k$ people from $n$ and a person to run that committee in two ways. First, choose the committee and then someone to run it from amongst those people. There are
$$\binom{n}{k} k \qquad \text{ ways to do this.}$$
On the other hand, you could fist choose the person to run the committee, and then choose the other $k-1$ members from the remaining $n-1$ people. There are
$$\binom{n-1}{k-1} n \qquad \text{ ways to do this.}$$
Since $\binom{n}{k} k$ and $\binom{n-1}{k-1} n $ are two different ways of expressing the size of the same set, they must be equal.
\end{ans}
\item Illustrate your combinatorial proof using the set $A = \{a,b,c\}$ (so that $n=3$) and $k=2$.
\begin{ans}
In the first way of counting, we have
\begin{align*}
&\text{committee $\{a,b\}$ with leader $a$,}\\
&\text{committee $\{a,b\}$ with leader $b$,}\\
&\text{committee $\{a,c\}$ with leader $a$,}\\
&\text{committee $\{a,c\}$ with leader $c$,}\\
&\text{committee $\{b,c\}$ with leader $b$, and} \\
&\text{committee $\{b,c\}$ with leader $c$.}
\end{align*}
In the second way of counting, we have
\begin{align*}
&\text{leader $a$ with other member $b$,}\\
&\text{leader $b$ with other member $a$,}\\
&\text{leader $a$ with other member $c$,}\\
&\text{leader $c$ with other member $a$,}\\
&\text{leader $b$ with other member $c$, and }\\
&\text{leader $c$ with other member $b$.}\\
\end{align*}
Either way, there are 6 choices.
\end{ans}
\item Verify the identity algebraically using the formula $\binom{n}{k} = n!/((n-k)!k!)$.
\begin{ans}
Algebraically, we have
$$\binom{n}{k} k = \frac{n!}{((n-k)!k!}k
= \frac{n!}{((n-k)!(k-1)!}
= \frac{n*(n-1)!}{((n-1)-(k-1))!(k-1)!} = n\binom{n-1}{k-1}.$$
\end{ans}
\end{enumerate}
\end{enumerate}
\end{try}
\end{document}