\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 3}
\centerline{February 17, 2017}
\vskip 10pt
\noindent
3.1.13.  There are $\binom{5}{2}$ ways to choose the senior members and $\binom{100}{3}$
to choose the junior members.  By the multiplication principle, the number is
$$\binom{5}{2} \cdot \binom{100}{3} = 10\cdot 161,700 = 1,617,000.$$
\vskip 10pt
\noindent
3.1.14.  There are 5 choices for the bun, 8 choices for the patty, 5 choices for the cooking method, 
$$\binom{10}{0} + \binom{10}{1} + \binom{10}{2} + \binom{10}{3} = 1 + 10 + 45 + 120 = 176$$
different choices for the cheese(s), $2^8 = 256$ different combinations of vegetables, 
and 
$$\binom{13}{0} + \binom{13}{1} + \binom{13}{2} + \binom{13}{3} + \binom{13}{4} =
1 + 13 + 78 + 286 + 715 = 1093$$
combinations of up to 4 condiments.
By the Multiplication Principle, the total number of different burgers you can order is
$$5 \cdot 8 \cdot 5 \cdot 176 \cdot 256 \cdot 1093 = 9,849,241,600$$
different burgers.    (``Burgero Magnifico'' indeed, but one 
wonders how many of those different possibilities have ever
been ordered!)
\vskip 10pt
\noindent
3.1.17.  (See Proposition 3.8)  
In the $8$ distinct numbers, there are $\binom{8}{2} = 28$ different pairs, but
some of the pairs contain the same element. 
As in the proof given in the text, 
we'll say two pairs $a,b$ and $a,c$ overlap at $a$ if $b - a = a - c$, or $b + c = 2a$.
If we have additional pairs $a,b'$ and $a,c'$ overlapping at the same $a$ and $b,c,b',c'$
are all distinct, 
then $b + c = 2a = b' + c'$ and we have found what is asked for.  So without
loss of generality, we may assume there are at most two overlapping $a,b$ and $a,c$ pairs at each $a$.  
At each $a$ in the set where overlapping pairs exist, we \emph{remove one of the pairs}.
Since we had $28$ pairs to begin with and there are at most $8$ such $a$, there are at least
$28 - 8 = 20$ remaining pairs.  
We subtract the smaller number in the pair from the larger number in each case.  Since
the numbers are coming from $[20]$, they elements of a pair differ by at most 19.  This 
gives at most 19 possibilities for the difference.  By the Pigeonhole Principle, two different
pairs must have the same difference, so there are pairs $a > d$ and $c > b$ among the 8 numbers
such that $a,b,c,d$ are distinct and $a - d = c - b$.  But then $a + b = c + d$.  
\vskip 10pt
\noindent
3.1.19. (Extra Credit) As stated, the problem seems to be defective.
First, we must clearly have $n \ge 15$ in order to have at least 15 distinct
elements in $[n]$.  If $n = 15$ then there are also clearly distinct $a,b,c,d$ in $[15]$ itself
for which $a + b = c + d$.  Take $a = 1, b = 15$, $c = 2, d = 14$ for instance.  So
the \emph{smallest} $n$ for which this is true is $n = 15$, but this seems like a silly 
thing to be asking about.  I have the feeling that the author meant ``largest''
instead of ``smallest.''
  There are $\binom{15}{2} = \frac{15(15-1)}{2} = 105$ pairs.  As in the solution 
for 3.1.17 we are done if our set contains $a$ and $b,c,b',c'$ distinct
such that $b - a = a - c$ and $b' - a = a - c'$.  So we may assume that there is at
most one such overlap for each $a$ in the set and we remove one of the pairs, leaving
at least $105 - 15 = 90$ pairs.  If we subtract the
smaller from the larger, we get at least 90 differences.  We want to be able to apply
the Pigeonhole Principle as in the last problem, so we want $90 > n - 1$, so $n < 91$.  
$n = 90$ is the largest $n$ for which this argument will work.   It is not hard to 
construct subsets of $[n]$ of size 15 for which $a + b \ne c + d$ whenever
$a,b,c,d$ are distinct and $n$ is large enough.  Do you see how?
\vskip 10pt
\noindent
3.2.6.  The denominations of the two pairs can be any two distinct denominations out
of the 13 in the deck so there are $\binom{13}{2}$ ways to pick those.  Within
the denominations, the pairs can be from any two of the suits, so there are $\binom{4}{2}$
ways to choose the suits of the first pair and $\binom{4}{2}$ ways to choose the
suits in the second pair.  Then the fifth card in the hand must be a card in one of the
11 other denominations \emph{not} represented in the two pairs; there are $11\cdot 44$
ways to choose that last card.  So by the Multiplication Principle
the total number is
$$\binom{13}{2}\cdot \binom{4}{2}\cdot \binom{4}{2} \cdot 44 = 123,552.$$
\vskip 10pt
\noindent
3.3.6.  
\begin{enumerate}
\item[(i)]  $\binom{6}{3}y^3 = 20y^3$.
\item[(ii)]  $\binom{7}{3}\cdot 3^4 = 2835$.
\item[(iii)]  $\binom{4}{3}\cdot 2^3\cdot 5 = 160$.  
\item[(iv)] Think of expanding like this: 
$$(2x + 3y + 5)^7 = \sum_{k=0}^7 \binom{7}{k} (2x)^k (3y + 5)^{7 - k}$$
So the coefficient of $x^3$ is 
$$\binom{7}{3}\cdot 2^3 \cdot (3y + 5)^4 = 280(3y + 5)^4.$$
\end{enumerate}
\vskip 10pt
\noindent
3.3.7.  From the binomial theorem we know 
$$(1 + x)^n = \sum_{k = 0}^n \binom{n}{k} x^k.$$
Differentiate both sides $m$ times with respect to $x$.  On the left we get
$$n(n-1)\cdots (n - m + 1)(1 + x)^{n-m} = P(n,m) (1 + x)^{n-m}.$$
on the right, the $m$th derivative of $x^k$ is just 
$$\begin{cases}
k(k-1)\cdots (k - m + 1)x^{k - m} = P(k,m)x^{k-m} & {\rm if}\ k \ge m\\
0 & {\rm if}\ k < m.
\end{cases}$$
Therefore, 
$$P(n,m)(1 + x)^{n-m} = \sum_{k=0}^n \binom{k}{n} P(k,m) x^{k-m}.$$
The desired equality then follows by setting $x = 1$:
$$P(n,m)\cdot 2^{n-m} = \sum_{k=0}^n \binom{k}{n} P(k,m).$$ 
Comment:  If $m > n$, then $P(n,m) = 0$ and $P(k,m) = 0$ for all $k$ with $0 \le k \le n$.
So the formula is true in those cases without any additional argument.
\vskip 10pt
\noindent
3.4.6.  Think of the process of choosing a committee of $k$ people from 
a pool of $n$ possible members, if one of the members is also singled out 
as a chairperson.  We can count the number of ways to do this in more than
one way.  First, there are $n$ choices for the committee chair, and then 
$\binom{n-1}{k-1}$ ways to choose the other $k -1$ members of the committee
Hence by the Multiplication Principle, we would have $n\cdot \binom{n-1}{k-1}$
to make the selection by that process.  Second, we could think of choosing
the committee first, with $\binom{n}{k}$ possible choices, and then electing
the chair from the membership, so $k$ choices.  Since these are two different
ways of counting the same collection of things, we have
$$n\cdot \binom{n-1}{k-1} = \binom{n}{k}\cdot k.$$
\vskip 10pt
\noindent
3.4.7.  Continuing from the previous problem, consider the problem
of counting a committee with a chairperson chosen from a pool of $n$
candidates.  The committee can have any number of members $1$ up to $n$.
So if we add the right hand sides in the last formula from 3.4.6 we get
the total number of committees with a chairperson counted one way:
$$\sum_{k=1}^n k\cdot \binom{n}{k},\ {\rm which\ equals}\ \sum_{k=0}^n k\cdot \binom{n}{k}$$
since the term with $k = 0$ is $0$.  Now on the other hand, to choose the committee
we could also pick the chairperson first, then any combination of the other $2^{n-1}$ people
to fill out the membership. By the Multiplication Principle the number of choices
is $n\cdot 2^{n-1}$. Again since we are counting the same collection of things in 
two different ways, we have
$$n\cdot 2^{n-1} = \sum_{k=0}^n k\cdot \binom{n}{k}.$$
\vskip 10pt
\noindent
3.5.5.  There are $\binom{n}{k}$ such strings because there are that many ways
to place the $k$ ones among the $n$ bits in the string and the other entries must
then be zeroes.  (Note:  This \emph{is not} a case to apply the ``dividers'' or ``stars and bars''
method.  Our author is being slightly devious to test your understanding and review previously
covered material!)
\end{document}
