% Math 320 hw2
%
\documentclass{article}
\pagestyle{empty}
\usepackage[textheight=10in]{geometry}

\usepackage{amsmath}
\usepackage{hyperref}
\usepackage{graphicx}
\usepackage{verbatim}

\newcommand{\coursehome}
{http://www.cs.umb.edu/~eb/320}

\title{Discrete Mathematics \\
Homework 2 Solutions
}
\author{Ethan Bolker \\ Matt Lehman}
%\date{September 1, 2014}

\begin{document}

\maketitle



\section*{Exercises}

\begin{enumerate}

\item Study the posted solutions to the first homework. 
Then write a sentence or two (or a paragraph or two) explaining what
you will do differently this time based on what you discovered there.  

\item How many permutations are there of the six letters in the word
  \verb!APPLES! ? 

We've seen this word before. To answer the question, first find out
how many ways there are to place the two \verb!P!s.

There are $\dbinom{6}{2}$ ways to place the two \verb!P!s, and $4!$ ways of permuting the remaining four letters for a total of \[  \dfrac{6!4!}{2!4!} = \dfrac{6!}{2!}  = 360. \]

\item How many permutations are there of the letters in the word
  \verb!BOOKKEEPER!? \footnote{Other than trivial variations
    ('bookkeepers' and 'bookkeeping'), this is the only word in the
    English language to have three consecutive sets of repeated
    letters.} 
  
If all ten letters were different, there would be $10!$ permutations.
To take into account the multiple counting of repeated letters, we
have to divide by the number of ways of permuting each repeated
letter.  Letters \verb!O! and \verb!K! each occur twice and letter
\verb!E! occurs three times, so the total number of permutations is \[
\dfrac{10!}{2!2!3!} = 151,200. \] 

You can do the previous problem this way too, and arrive at the same
correct answer.

\item How many permutations are there of the letters in the word
  \verb!BOOKKEEPER! in which the two \verb!O!s and the two
\verb!K!s are adjacent (but not necessarily next to each other).

If each of the two pairs of \verb!O!s and \verb!K!s are adjacent, we
can think of each of them as one letter, (\verb!OO! and \verb!KK!).
Now we're permuting eight ``letters'', with three repeated \verb!E!s,
which gives us a total of 
%
\[ 
\dfrac{8!}{3!} = 6,720 \text{\quad permutations.}
\]  

\item How many permutations are there of the string
  \verb!ABCDEFGGG! in which exactly two of the 
\verb!G!s are adjacent?

There are two ways to think about this.  First, consider a \verb!GG!
pair to be a single letter and count the permutations of the remaining
letters where the third \verb!G! isn't adjacent to the \verb!GG! pair.
We temporarily remove the single \verb!G! and see there are $7!$
permutations of the remaining letters.  In each of those there are
eight potential slots for the \verb!G!, but two are adjacent to
\verb!GG!, so only six are valid.  This gives us $6 \cdot 7! = 30,240$
permutations. 

A slightly easier way is to count all the permutations, and subtract
the ones that aren't allowed, namely the permutations where all three
\verb!G!s are consecutive.  The total is \[ \dfrac{9!}{3!}=60,480. \]
The invalid cases are when we have a \verb!GGG!, which we can pretend
is a letter.  This gives us 7! permutations that aren't allowed, for
an adjusted total of 
%
\[ 
\dfrac{9!}{3!} - 7! = 60,480 - 30,240 = 30,240
\text{\quad permutations, which agrees with our earlier result.} 
\]  

\item How many ways can $b$ books be placed on $s$ numbered shelves 

\textbf{I declared this problem too difficult, so you didn't have to
  solve it. Matt did; here's his solution. It's full of useful
  strategies.
}
\begin{enumerate}
\item if the books are indistinguishable copies of the same title?

When trying to solve math problems we've never seen before, sometimes
half the battle is choosing the best symbols to represent the problem.
Before we provide the solutions, let's take a step back and try to
look at a ``bigger picture'' of the different ways of counting. 

Most counting problems fall into two categories: the objects being
counted are distinct (different), or indistinct (identical).  If you
have $n$ distinct objects, then you might as well call them
$1,2,3, \ldots, n$.  If you have $n$ indistinct objects, then you might as
well think of them as $n$ copies of the number $1$. 

If you think of the numbers $1,2,3, \ldots, n$ as the elements of the
set $\{1,2,3, \ldots,n\}$, then breaking distinct objects into parts can be
thought of as ways of partitioning a set, or \emph{set partitions}.
If you think of $n$ objects as $n$ $1$s, then breaking indistinct
objects into parts can be thought of as partitioning an
integer \footnote {When counting, unless otherwise stated,
  when we say ``integer'', we really mean ``non-negative integer'', to
  save time and verbiage. When studying number theory, ``integer''
  includes the negatives.
}, or \emph{integer partitions}. 

If we're distributing $b$ indistinguishable books on $s$ numbered
shelves, then we're looking at ways of partitioning the number $b$
into $s$ parts.  This type of distribution is called a
\emph{composition}.  We're counting the number of ways an integer can
be broken up (or composed), \emph{where order matters}.  (Problem 17
is when order doesn't matter). 

\vspace{0.2in}
\textbf{Now Matt derives the formula for counting compositions, much
  the way we did it in class. So you can think of what follows as
  notes from that class.}
\vspace{0.2in}

As usual, let's try small numbers, say $b=5, s=3$.  We can think of
$5$ as $11111$, but how do we express the ways of breaking that up
into $3$ parts?  We do this by placing a delimiter (say $\vert$ or +)
among the $1$s.  Using $\vert$ conveys the idea of partitions, while +
conveys the idea of summands.  Since $\vert$ resembles a $1$, we'll
use +, but you might find $\vert$ to be easier to write on paper.
Some examples would be $11+11+1$ $(2,2,1),$ $1+1+111$ $(1,1,3)$ or
$1+11+11$ $(1,2,2).$   

Since we're used to the idea of choosing objects none at a time, we
should be comfortable with the idea that some parts of a composition
might be $0$.  Since we don't have a symbol for $0$, we'll express
this with two consecutive +s, denoting a $0$ in that part.  If the
first (or last) part is a $0$, then we'll begin (or end) with a +.
For example, a few more compositions could be $+111+11$ $(0,3,2)$,
$1+1111+$ $(1,4,0)$ or $11++111$ $(2,0,3).$ 

If you look at all the strings of $1$s and +s, it should be clear why
we always have five $1$s, but notice that we only have two +s, not
three.  This is because wherever the two +s are, we have three
partitions: the $1$s before the first +, between the first and second
+ and after the second +. 

It should also be clear that every permutation of $1$s and +s is a
unique composition, and conversely, every composition is a unique
permutation of $1$s and +s.  So now we see that counting compositions
is the same as counting permutations of $1$s and +s, where the number
of $1$s $=n$ and the number of +s = number of parts, minus 1. 

We can now state that the number of compositions of $n$ into $k$ parts
is \[ \dfrac{(n+k-1)!}{n!(k-1)!} = \dbinom{n+k-1}{k-1} =
\dbinom{n+k-1}{n}. \] 

Let's try a sanity check for extreme values for $k$ and $n$ and see if
they make sense.  If $k=1$ then we're counting compositions of $n$
into one part.  There should only be one way to do this, and if we
plug $k=1$ into  
%
\[ \dbinom{n+k-1}{k-1} \text{ we get }\dbinom{n}{0} = \dbinom{n}{n} =
1, 
\] 
%
so this makes sense.

If $n=1$, we're composing $1$ into $k$ parts.  This might sound
strange, but there's nothing wrong.  We're used to working with $n$
and $k$ as counting subsets where $k\le n$, but we no longer have that
restriction here, as long as $k>0$ and $n\ge 0.$  In this case, we're
going to have one of the $k$ parts with $1$ and the rest with $0$s, so
there should be $k$ ways to do this.  Plugging $n=1$ into  
%
\[ 
\dbinom{n+k-1}{n} \text{ we get }\dbinom{k}{k-1} = \dbinom{k}{1} =
k, 
\] 
so this makes sense.

Finally, if we let $n=0$, then there should be only one way to compose
$0$ into $k$ parts, namely $k$ $0$s.  Letting $n=0$ 
%
\[ 
\dbinom{n+k-1}{n} = \dbinom{k-1}{k-1} =\dbinom{k-1}{0} = 1,
\]
%
so this also makes sense.


In the original problem, $n=b$ and $k=s$, so this becomes 
%
\[
\dfrac{(b+s-1)!}{b!(s-1)!} = \dbinom{b+s-1}{s-1} =
\dbinom{b+s-1}{b}. 
\] 

In our example, $b=n=5$ and $s=k=3$, so the number of those
compositions would be 
%
\[ \dfrac{(5+3-1)!}{5!(3-1)!} = \dbinom{7}{2} =
\dbinom{7}{5} = 21. 
\] 

This is a relatively small number, so you are encouraged to list them all.

\item if no two books are the same, but the positions of the books on
  each shelf don't matter?
  
  Now the objects are distinct, so we should think of them as a set
  with elements $\{1,2,3,\dots, b\}$ 
  
  We can place book \#1 in $s$ places.  Since the relative positions
  of the books on a shelf don't matter, then we also have $s$ places
  for book \#2.  The same argument holds for all the books, since the
  number of ways of placing each book is independent from the rest.
  Therefore, we have $s^{b}$ different arrangements. 
  
  More generally, if we have $k$ distinct objects going into $n$ sets,
  where the order of the sets matters (but not the order within the
  set), the total number of arrangements $= n^{k}.$ 
  
\item if no two books are the same, and the positions of the books on 
  each shelf matter?
  
  To solve this problem, we'll first take the ``scenic route'', where
  we'll encounter some new ideas which you might see in future
  classes, and see how they relate.  Finally, we'll how the answer
  ties into a recent result. 
  
  We can place book \#1 in $s$ places.  We can place book \#2 in $s-1$
  places where there are empty shelves and also either before or after
  book \#1, giving us $(s-1)+ 2 = s+1$ places.  Each time we add a
  book, we increase the number of places we can place the next book by
  one.  Therefore, the number of arrangements is
  $s(s+1)(s+2)\cdots(s+b-1).$  This looks like a strange kind of
  factorial, where each factor increases by one, unlike $n!$, whose
  factors decrease by one, until we reach the number 1.  This
  increasing product is called a \emph{rising factorial}.  If we start
  with $n$ and have a total of $k$ terms, each one more than the last,
  this is denoted as $n^{\overline{k}}$.  In our problem, the number
  of arrangements is $s^{\overline{b}}.$ 
%  
\[
n^{\overline{k}} = n(n+1)(n+2)\cdots(n+k-1).  
\]
  
We can also express a rising factorial as the quotient of two factorials.
  
\[ 
n^{\overline{k}} = \dfrac{(n+k-1)!}{(n-1)!} \text{\quad or \quad}
n^{\overline{k+1}} = \dfrac{(n+k)!}{(n-1)!} \text{\quad or \quad}
(n+1)^{\overline{k}} = \dfrac{(n+k)!}{n!}=k!\dbinom{n+k}{n}
\]  
  
  Just as we have the concept of a rising factorial, we can also have
  a \emph{falling factorial}.  In this case, we have a product of $k$
  terms, beginning with $n$, but with each term one less than the
  last.  In this case we end with the term $n-k+1$, in general not
  equal to $1$.  We can think of this as a truncated factorial, since
  we usually stop before $1$.  In this sense this is a more natural
  generalization of $n!$ than the rising factorial.  This is expressed
  as $n^{\underline{k}}$ and is defined as 
%
\[ 
n^{\underline{k}} =   n(n-1)(n-2)\cdots(n-k+1). 
\] 
  
  We can also express a falling factorial as the quotient of two
  factorials, which should look familiar. 
%    
\[ n^{\underline{k}} = \dfrac{n!}{(n-k)!}  = k!\dbinom{n}{k}
\]
    
    This is the number of ways of taking a subset of size $k$ from a
    set of size $n$, where the order of the elements in the $k$ subset
    matters.  
    
  
  You should see that 
\[
n^{\overline{1}} = n^{\underline{1}} = n
  \text{\quad and that }n^{\underline{n}} = n!
\] 
%
What is $ n^{\underline{n+1}}$?
 
  We can also define a falling factorial in terms of a rising
  factorial, where we have $k$ terms, starting with the largest term
  $n$, ending with $n-k+1$ and reverse the order:
\[
 n^{\underline{k}} = n(n-1)(n-2)\cdots(n-k+1) = (n-k+1)(n-k+2)\cdots
  (n-1)n = (n-k+1)^{\overline{k}}
\] 
    
  Conversely, we can also express a rising factorial in terms of a
  falling factorial, where we have $k$ terms, starting with the
  smallest term $n$ and ending with $(n+k-1)$ and reverse the
  order:
\[ n^{\overline{k}} = n(n+1)(n+2)\cdots(n+k-1) =
  (n+k-1)(n+k-2)\cdots(n+1)n = (n+k-1)^{\underline{k}} 
\] 
  
  Since the falling factorial is a more natural idea, rising
  factorials are frequently expressed in terms of falling factorials:

\[
n^{\overline{k}} = (n+k-1)^{\underline{k}} = \dfrac{(n+k-1)!}{(n-1)!}
=  k!\dbinom{n+k-1}{k} = k!\dbinom{n+k-1}{n-1}
\]
  
  Recalling the original problem, the answer would be 
%
\[
  s^{\overline{b}} = (s+b-1)^{\underline{b}} =
  \dfrac{(s+b-1)!}{(s-1)!}  = b!\dbinom{s+b-1}{b}
\] 
  
  This should look familiar.  Recall that the number of compositions
  of $n$ into $k$ parts is
%
\[
\dbinom{n+k-1}{k-1} = \dbinom{n+k-1}{n} 
\]
%  
and the number of ordered subsets of size $k$ from a set size $n$ is
%
\[
\dfrac{n!}{(n-k)!}  = k!\dbinom{n}{k} 
\] 
%  
so this is also the number of compositions of $n$ into $k$ \emph
{ordered} subsets.  Instead of looking at ordered integer partitions
(compositions), we're looking at ordered set partitions.  If we took
our result
%
\[ 
b!\dbinom{s+b-1}{b} 
\]  
%  
and pretended all the books were identical, then we would have to
divide by $b!$, which would give us the answer for part
a):
%
\[
\dbinom{s+b-1}{b} 
\] 
  
  If you saw the connection between problems a) and c), without going
  the long way, then you have good intuition. 
  
  \end{enumerate}

\item How many ways are there to deal hands of seven cards to each of
  five players from a standard deck of $52$ cards?

Traditionally, each player is dealt one card, then two, until each has
the requisite number of cards.  Equivalently, the first player can
receive all seven cards, then the second, and so on.  The second way
is easier to work with.  It should also be clear that the order of the
cards in each player's hand isn't relevant.  There are 
%
\[
\dbinom{52}{7} 
\]
%
ways of dealing seven cards to the first player.
Now that the deck has 45 cards, there are 
%
\[
\dbinom{45}{7} 
\]
%
ways of dealing the next seven cards to the second player.  If we
continue with all five players, we'll have the following total number
of possibilities:
%
\[
\dbinom{52}{7}\dbinom{45}{7}\dbinom{38}{7}\dbinom{31}{7}\dbinom{24}{7} 
\]

If we expand, we can see there will be some cancellations:
%
\[
\left(\dfrac{52!}{7!45!}\right)\left(\dfrac{45!}{7!38!}\right)
\left(\dfrac{38!}{7!31!}\right)\left(\dfrac{31!}{7!24!}\right)
\left(\dfrac{24!}{7!17!}\right) 
= \left(\dfrac{52!}{17!(7!)^{5}}\right) \approx 7*10^{34}  
\]
\footnote{Matt suggests that you might want to check his calculation.}

The number of $5$-card poker hands is
%
\[ \dbinom{52}{5} = 2,598,960. 
\]

A common combinatorial exercise is to count how many ways there are to
get each kind of poker hand (1 pair, 2 pair, 3 of a kind, 4 of a kind,
full house, straight, flush, straight flush and royal flush) and rank
them by frequency.  We won't have time for that, but you're encouraged
to figure them out.  Note: generally the more common the hand, the
harder it is to count -- not because there are more possibilities, but
because you have to make sure you're not double counting a rarer
hand. 

\item How many subsets of a $20$ element set contain exactly $4$
  elements? How many contain at most $4$ elements?
  
  For the first part, this is simply 
%
\[
\dbinom{20}{4} =   \dfrac{(20)(19)(18)(17)}{4!} = 4,845.  
\] 
  
  For the second part, this is 
%
\[
  \dbinom{20}{0}+\dbinom{20}{1}+\dbinom{20}{2}
+\dbinom{20}{3}+\dbinom{20}{4}=1+20+190+1,140+4,845
  = 6,196.
\] 

What if the problem asked how many subsets contain \emph{at least} $4$
elements? 

\item If you flip a fair coin $20$ times, what is the probability that
  you get exactly $4$ heads? At most $4$ heads?

The probability is the number of ways of picking four heads out of
$20$ flips, times the probability of getting $4$ heads and $16$ tails.
Let $p$ = probability of a head and $q$ = probability of a tail.
Since we have a fair coin, $p=q=\frac{1}{2}$:
%
\[
\dbinom{20}{4}\left(\dfrac{1}{2}\right)^{20} =
\dfrac{4,845}{2^{20}}\approx  0.46\%
\] 

The probability of getting at most $4$ heads is
%
\[
\left(\dfrac{1}{2}\right)^{20}\left[\dbinom{20}{0}
+\dbinom{20}{1}+\dbinom{20}{2}+\dbinom{20}{3}+\dbinom{20}{4}\right]= 
\dfrac{6,196}{2^{20}}\approx 0.59\%
\] 

\item How many numbers less than one million have exactly four ones
  in their binary representation? What are the largest and smallest
  such numbers?
  
Since $2^{10}\approx 1,000$ then $2^{20}\approx 1,000,000$.  We know
this is an underestimate, so $999,999$ has $20$ digits in binary.  If we
allow for all $20$ digits to be used (which might give us numbers too
large), then the answer is again
%
\[
\dbinom{20}{4}=4,845. 
\]
%
The
largest of these is $11110000000000000000_{2} =
2^{19}+2^{18}+2^{17}+2^{16} = 2^{16}(8+4+2+1)= 15*2^{16} = 983,040$,
so we didn't overshoot.  The smallest is $1111_{2} = (8+4+2+1) =15$ .

\item The roads in a city are laid out on a square grid with numbered
  Streets and Avenues, so each corner is defined as the intersection
  of a Street and an Avenue. For example, $(2,4)$ is the corner of
  Second Street and Fourth Avenue.

  Let $T(m,n)$ be the number of ways to walk from $(1,1)$ to $(m, n)$
  so that  at each stage either the Street number or the Avenue number
increases. For example, here are two of the $T(2,4) = 4$ ways to get
to $(2,4)$: 
% This commented line tells TeX not to start a new paragraph
\begin{equation*}
(1,1) \rightarrow
(1,2) \rightarrow
(2,2) \rightarrow
(2,3) \rightarrow
(2,4)
\end{equation*}
%
\begin{equation*}
(1,1) \rightarrow
(1,2) \rightarrow
(1,3) \rightarrow
(2,3) \rightarrow
(2,4)
\end{equation*}

Find a closed form expression for $T(m,n)$. You may want to start by
computing some small examples.

All paths have $m-1$ rightward components and $n-1$ upward components,
for a total length of $(m-1)+(n-1)= m+n-2.$  Each path is determined
by which of the $m+n-2$ steps goes right, or goes up.  You should see
that choosing the rightward steps determines the upward ones, and vice
versa.  Looking at the rightward steps, we see that each way to choose
the $m-1$ rightward steps from the total path length of $m+n-2$
determines a unique path, and also each unique path has a different
choice of rightward steps.  The same argument holds if we just
consider upward steps.  Therefore
%
\[
T(m,n) = \dbinom{m+n-2}{m-1} = \dbinom{m+n-2}{n-1}.
\] 

If we take another sanity check and see what happens if either $m$ or
$n=1$, we would get a one-dimensional path, which would have no
degrees of freedom and only one possibility.  We see that
%
\[
T(1,n)=T(m,1) = \dbinom{m+n-2}{0} = \dbinom{m+n-2}{0} = 1,
\]
%
independent of $m$ or $n$.

\item An identity.
%
Let
\begin{equation*}
M(n) = \sum_{j=1}^n j \binom{n}{j}.
\end{equation*}

\emph{That identity is correct -- because I fixed a typo. This was the
  original:}

\begin{equation*}
M(n) = \sum_{j=1}^n n \binom{n}{j}.
\end{equation*}

\begin{itemize}
\item Calculate the first few values of $M$.

\[  M(1) = 1\binom{1}{1} = 1\]

\[  M(2) = 1\binom{2}{1} + 2\binom{1}{2} = 4 \]

\[  M(3) = 1\binom{3}{1} = 2\binom{3}{2}+3\binom{3}{3}= 3+6+3 = 3(1+2+1)= 3(4) =12\]

\[  M(4) = 1\binom{4}{1} + 2\binom{4}{2} +3\binom{4}{3} +4\binom{4}{4} = 4+12+12+4= 4(1+3+3+1) =4(8)=32\]

\[  M(5) = 1\binom{5}{1} +2\binom{5}{2} +3\binom{5}{3} +4\binom{5}{4} +5\binom{5}{5} =  \]
\[ 5+20+30+20+5 = 5(1+4+6+4+1)= 5(16)=80\]


\item Guess the pattern. Here's a hint: look at $M(n+1)/2M(n)$.

If you didn't see the pattern, here are the first few terms of $M(n+1)/2M(n)$
\[\dfrac{M(2)}{2M(1)} = \dfrac{4}{2(1)}= 2\]
\[\dfrac{M(3)}{2M(2)} = \dfrac{12}{2(4)}= \dfrac{3}{2}\]
\[\dfrac{M(4)}{2M(3)} = \dfrac{32}{2(12)}= \dfrac{4}{3}\]
\[\dfrac{M(5)}{2M(4)} = \dfrac{80}{2(32)}= \dfrac{5}{4}\]

So it seems that a good guess for $M(n+1)/2M(n)$ is $(n+1)/(n)$

Based on that ratio, we see that dividing by 2 keeps the expression
stable, it looks that $M(n)$ doubles with $n$, so it should have a
power of $2$.  Factoring that out, $M(n)$ seems to grow like $n$, so a
reasonable guess is that $M(n)= n(2^{n}),$ or $n(2^{n-1}),$ or
$n(2^{n+1}).$ 

You might've seen the pattern that each sum was expressed as $n$(sum
of the $(n-1)$th row of Pascal's Triangle). 

\item Guess a closed form expression for $M(n)$.

If you used the first way, then by trial and error, you probably came
to the same conclusion as if you used the second way, namely $M(n) =
n(2^{n-1}).$ 


\item Prove that your guess is correct. Here are hints for two different
  proofs - do both if you can. (1) Use the binomial theorem and differentiate
  $(1+x)^n$. (2) Try induction.


1) The binomial theorem says that 

\[ (x+y)^{n} = \sum_{j=0}^{n}\dbinom{n}{j}(x^{j}y^{n-j}) \]  

Setting $y=1$, we have

\[  (x+1)^{n} = \sum_{j=0}^{n}\dbinom{n}{j}x^{j}\]

Note that $j$ starts at $0$, but $M(n)$ has $j$ starting at $1$.  This
turns out to be no problem, because we can let $j$ start with $0$
without changing the sum.  (Do you see why?). 

You might also be wondering why we're differentiating the binomial
theorem.  $M(n)$ is the sum of binomial coefficients, suggesting that
the binomial theorem will be involved, but we need to introduce the
$j$ coefficient somehow.  Since the binomial theorem is the sum of
$x^{j}s$, differentiating will bring down the $j$. 

\[
\dfrac{d}{dx}(x+1)^n = n(x+1)^{n-1} =
\dfrac{d}{dx}\sum_{j=0}^{n}\dbinom{n}{j}x^{j} = \sum_{j=0}^{n}j
\dbinom{n}{j}x^{j-1} 
\]
%
so we have 
%
\[ 
\sum_{j=0}^{n}j \dbinom{n}{j}x^{j-1} = n(x+1)^{n-1} 
\]
%
Substituting $x=1$,
%
\[
\sum_{j=0}^{n}j \dbinom{n}{j} = \sum_{j=1}^{n}j \dbinom{n}{j} =
n(2^{n-1}). 
\]


2) \textbf{Here is Matt's induction. It's not pretty -- I should have
  tried it myself before I asked you to!}

\vspace{0.2in}


We want to prove that 
\[ M(n) = \sum_{j=1}^n j \binom{n}{j} = n(2^{n-1}), \text{for all $n$.} \]

Let $n=1$ be our base case.  $M(1) = 1(2^{1-1}) = 1(1) = 1.$  So our base case works.

We assume this is true for a given $n$.  Now we have to show this is true for $n+1$.

Given that $M(n) = n(2^{n-1}),$ proving that $M(n+1) = (n+1)2^{n}$ is
equivalent to proving
\footnote{The \LaTeX{} equations that follow should be formatted with
  the align* environment.}


\[M(n+1)- M(n) = (n+1)2^{n} - n(2^{n-1}) = (2^{n-1}(2(n+1)-n))=2^{n-1}(n+2).\]

\[  M(n+1) = \sum_{j=1}^{n+1} j \binom{n+1}{j} = \sum_{j=1}^{n} j \binom{n+1}{j} + (n+1)\dbinom{j+1}{j+1} = \sum_{j=1}^{n} j \binom{n+1}{j} + (n+1)\]

\[ M(n+1)-M(n) =  \sum_{j=1}^{n} j \binom{n+1}{j} + (n+1)- \sum_{j=1}^{n} j \binom{n}{j}=\]

\[ (n+1) + \sum_{j=1}^{n} j \left[ \binom{n+1}{j}- \binom{n}{j}\right]\]

Let's focus on the binomial coefficients.

\[
\binom{n+1}{j}- \binom{n}{j} =
\left[\dfrac{(n+1)!}{j!(n+1-j)!}-\dfrac{n!}{j!(n-j)!}\right]=
\]
\\
\[ \dfrac{(n+1)!-n!(n+1+j)!}{j!(n+1-j)!}= \dfrac{n!((n+1)-(n+1-j))}{j!(n+1-j)!}=\]
\\
\[\dfrac{n!j}{j!(n+1-j)!}= \dfrac{n!}{(j-1)!(n+1-j)!} = \dbinom{n}{j-1} \]

\[  \text{Inserting back into the summation, } M(n+1)-M(n) = (n+1) + \sum_{j=1}^{n} j \binom{n}{j-1}=\]

\[ (n+1)+\sum_{j=1}^{n} (j-1) \binom{n}{j-1} + \dbinom{n}{j-1}=\]

\[ (n+1)+\sum_{j=1}^{n} (j-1) \binom{n}{j-1} + \sum_{j=1}^{n}\dbinom{n}{j-1}=\]

Looking at the first summation, if $j$ were allowed to go to $n+1$,
then that would be $M(n)$, so the first term $=M(n)$ less when $j=n+1$
which is $n$, so the first summation $=M(n)-n$. 

Looking at the second summation, if $j$ were allowed to go to $0$,
then that would be $2^{n}$, so the second term $=2^{n}$ less when
$j=0$, which is $1$, so the second summation $=2^{n}-1.$  

\[ \text{This gives us } (n+1) +(M(n)-n)+(2^{n}-1)  =
n2^{n-1}+2^{n}=2^{n-1}(n+2), \text{and we're done.}\] 

\end{itemize}

\item  From the symmetry of the binomial coefficients, it is not too 
  hard to see that when $n$ is an odd number, the number of subsets of 
$\{1,2, \ldots, n\}$ of odd
size equals the number of subsets of
even size. Is that true when $n$ is even?
Why or why not?

The number is the same for even $n$ too. Here's why. Think about all
the subsets of $n-1$ and divide them into two equal piles -- the even
ones and the odd ones. These are also subsets of an $n$ element set --
the ones that don't contain the new guy who walks in the door. The
ones that do contain him you get by adding him to all the ones we
listed before. The odd ones become even and the even ones become odd,
so there are the same number of each of these kinds too.

Here's a second solution. In Pascal's triangle, the numbers in row $n$  
row alternate counting the number of even and odd subsets of an $n$
element set. Remember that the binomial theorem says
%
\begin{equation*}
(1+x)^n = \binom{n}{0}
+ \binom{n}{1}x
+ \binom{n}{2}x^2 + \ldots
+ \binom{n}{n}x^n .
\end{equation*}
%
Setting $x = -1$ tells us that for $n > 0$
\begin{equation*}
0 = (1-1)^n = \binom{n}{0}
- \binom{n}{1}
+ \binom{n}{2} - \ldots
\pm \binom{n}{n} .
\end{equation*}
%
Moving the negative terms to the other side of the equation proves the
identity we want.

Note: the assertion is false when $n=0$. The empty set has just one
subset, itself, which has an even number of elements ($0$ is even). It
has no subsets with an odd number of elements.

\item Apples and bananas

\vspace{0.2in}
\textbf{We spent a full class on this an the next few questions, and
  Matt answered it above, so there are no new answers here.}
\vspace{0.2in}

Kids in first grade spend a fair amount of time mastering
  addition of small numbers by answering questions like

\begin{quotation}
If you have some apples and some bananas and you have $10$ pieces of
fruit altogether, how many of each might you have?
\end{quotation}

They work at listing all the possible answers to this question. They
use $10$ more often than any other total since combinations making
$10$ are the most important when learning arithmetic.

\begin{enumerate}
\item How many ways solutions are there for $n$ pieces of fruit?

\item The kids often ask (as they should!) whether it's OK to have
  \emph{no} apples. Which answer makes the most mathematical sense?

\item Answer the first question both when $0$ is allowed as a summand
  and when it's not.
\end{enumerate}

\item Apples, bananas and cherries.

Ask and answer the questions in the previous exercise for three kinds
of fruit.

\item Apples, bananas, cherries, dates, eggplants, \ldots

\begin{itemize}

\item How many ways are there to write $n$ as the sum of an ordered list of
$k$ nonnegative integers? 

We spent a full day on this in class. The answer is
\begin{equation*}
\binom{m+n-1}{n-1} .
\end{equation*}

You can think of that as the number of ways to place $n-1$ dividers in
$m+n-1$ spaces; you count the other spaces to find the size of each of
the $k$ summands.

Luke Chen pointed out in class that Problem 11 is essentially the same
problem. Look at the vertical steps as the dividers and the horizontal
steps as counting the sizes of the summands, row by row. You need to
use one extra row to get the total right.

\item How many ways are there to write $n$ as the sum of an ordered list of
$k$ positive integers?

\item (Trick question) How many ways are there to write $n$ as the sum
  of an ordered list of $k$ integers?

Infinitely many. For example, when $k=2$ we have
%
\begin{equation*}
n = (n-1) + 1 = (n-2) + 2 = \cdots = (n-n) + n = -1 + (n+1) = \cdots
\end{equation*}
\end{itemize}

\item The previous questions are all \emph{much harder} if the list
  isn't ordered. Then $3+7$ and $7+3$ count as the same way to sum to
  $10$.  Each way to write $n$ is a \emph{partition} of $n$.
 
  Let $P(n)$ be the number of partitions of $n$. Find the  first few
  values of $P(n)$ and then look up the sequence at the On-Line
  Encyclopedia of Integer Sequences (\url{http://oeis.org/} and
  \url{http://oeis.org/wiki/Welcome}). 

$1=1$ so $P(1) = 1$.

$2 = 1+1$ so $P(2) = 2$.

$3 = 1+2 = 1+1+1$ so $P(3) = 3$.

$4 = 1+3 = 2+2 = 1+1+2 = 1+1+1+1$ so $P(4) = 5$.

$5 = 1+4 = 2+3 = 1+1+3 = 1+2+2 =1+1+1+2 = 1+1+1+1+1$ so $P(5) = 7$

Searching the on line encylopedia for $1,2,3,5,7$ finds $754$
sequences. The first of these is the sequence of counts of
partitions. It continues
\begin{equation*}
1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, \ldots
\end{equation*}

\end{enumerate}

\newpage

\verbatiminput{\jobname}

\end{document}




