% 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
}
\author{Ethan Bolker}
%\date{September 1, 2014}

\begin{document}

\maketitle

\noindent
Due: Tuesday, September 30.

\section*{Preliminaries}

\begin{itemize}

\item Here's how to write binomial coefficients in \LaTeX:
%
\begin{center}
\verb! {a \choose b}!: ${a \choose b}$
\quad
\verb! \binom{a}{b}!: $\binom{a}{b}$
\end{center}

\item Some of these exercises are routine. Some are almost baby
  research problems. Do the best you can. I don't expect anyone to do
  them all!

\item Truth in advertising. Some of the routine problems come from
  several standard Discrete Mathematics texts. I haven't credited them
  individually since they don't really represent significant
  intellectual effort on the part of their authors.

\item   This quote From G. K. Chesterton's \emph{The Scandal of Father
    Brown} may help you remember that the start of every counting problem is
  understanding exactly what it is you have been asked to count. Work
  out some small cases by brute force -- don't just guess a formula
  and hope you're right.

\begin{quotation}
Father Brown laid down his cigar and said carefully: ``It isn't that they
can't see the solution. It is that they can't see the problem.''
\footnote{\url{http://gutenberg.net.au/ebooks02/0201031.txt}}
\end{quotation}

\item Submit \LaTeX{} source as usual as part of your document. Be sure to use hard carriage returns so I can read all your source code. I haven't done that here!
\footnote{Why is ``enter'' on your keyboard sometimes called
  ``carriage return''?}


\item Delete these preliminaries.

\end{itemize}
\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.

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

\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).

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

\item How many ways can $b$ books be placed on $s$ numbered shelves 
\begin{enumerate}
\item if the books are indistinguishable copies of the same title?
\item if no two books are the same, but the positions of the books on
  each shelf don't matter?
\item if no two books are the same, and the positions of the books on
  each shelf matter?
\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?

\item How many subsets of a $20$ element set contain exactly $4$
  elements? How many contain at most $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?

\item How many numbers less than one million have exactly four ones
  in their binary representation? What are the largest and smallest
  such numbers?


\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.

\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$.
\item Guess the pattern. Here's a hint: look at $M(n+1)/2M(n)$.
\item Guess a closed form expression for $M(n)$.
\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.
\end{itemize}

\item \label{problem:oddandevensubsets}
 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?

\emph{Hint:} Think about a recursive/inductive condition like the one
we used in class to count the total number of subsets of an $n$
element set when we knew the answer for an $n-1$ element set.

\item Apples and bananas

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.


\emph{Hint:} The hint at Problem~\ref{problem:oddandevensubsets} may
help here too. Think about solutions that use no apples.

\emph{Hint:} Do you recognize any binomial coeffiecients? (The numbers
in the first few rows of Pascal's triange should be your friends.)

\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? 

\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?
\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}). 
\end{enumerate}

\newpage

\verbatiminput{\jobname}

\end{document}




