\documentclass{article}
\input{../notes/preamble.tex}
\usepackage{url}
\usepackage{enumerate}
\title{Assignment 7}
\date{Friday June 23, 2012}
\newcommand{\df}{\textbf}
\begin{document}
\maketitle
\section{Counting}
This section is intended to be completed Tuesday June 20th. Here we will practice all the basic counting techniques we have learned. Fully explanations of how one counted is necessary for {\bf any} points. One can leave your final answer in terms of basic operations (factorials, combinations, multiplication, addition, subtraction, exponentiation are all fine)
\begin{prob}
Let $A$ be a finite set of size $n$
\begin{quote}
\begin{enumerate}[(a)]
\item Count the number of subsets of $A$ of size $k$
\item Use the above and rule of sums to count the number of subsets of $A$.
\item Recall we already proved $|\wp(A)|=2^n$. Equate the formula you got from the last part and $2^n$.
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
At a party there are $15$ men and $20$ women.
\begin{quote}
\begin{enumerate}[(a)]
\item How many ways can they form $15$ couples consisting of $1$ man and $1$ woman?
\item How many ways can they form $10$ couples consisting of $1$ man and $1$ woman?
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
Suppose there are $n$ people at a dinner party.
\begin{quote}
\begin{enumerate}[(a)]
\item Count the number of ways they can sit at a circular table. Note, the only thing that distinguishes an arrangement is the relative position of the people (eg. an arrangement where Bob is between Alice and Charlotte is different than if he's between Alice and Chuck).
\item Alice hates Bob. Count the number of ways the $n$ people can sit at the circular table so Alice doesn't have to sit next to Bob.
\item Alice changed her mind. She likes Bob now, but doesn't want him to be too close to the right side of her face. Count the number of ways $n$ people can sit at the circular table so that Bob doesn't sit next to Alice's right.
\item Alice and Bob decided they're best friends now. Count the number of ways to arrange them so that Alice and Bob do sit next to each other (he can sit to her right or left).
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
A woman is on the southwest corner of a city at 1st Street and 1st Avenue in a city with a nice city grid (not Pittsburgh, for example). She wants to get to 20th Street and 5th Avenue only moving one block at a time east and north. How many ways are there to do this?
\end{prob}
\begin{prob}
Consider binary strings of length $2n$.
\begin{quote}
\begin{enumerate}[(a)]
\item Count the number of strings.
\item Count the number of strings, where there are exactly $n$ ones.
\item Count the number of strings, where there are exactly $n$ ones and none are consecutive.
\end{enumerate}
\end{quote}
\end{prob}
\section{More Counting}
This section is intended to be completed Wednesday June 21st.
\begin{prob}
Count:
\begin{quote}
\begin{enumerate}[(a)]
\item The number of ways to arrange the letters in the word ADDRESSES.
\item The number of ways to put $10$ distinguishable balls in $3$ distinguishable bins, such that the first bin has $3$ balls, the second has $2$, and the third has $5$.
\item Do the same as part (b), but with indistinguishable balls.
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
You're going to a donut shop, and you gotta buy a dozen donuts. There are $5$ different varieties.
\begin{quote}
\begin{enumerate}[(a)]
\item How many ways are there to do this?
\item How many ways are there to do as in part (a), given that you want at least one chocolate?
\item How many ways are there to do as in part (a), given that there is only $2$ chocolate donuts left.
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
Consider the equation:
\[
x_1 + x_2 + x_3 + x_4 = 20
\]
\begin{quote}
\begin{enumerate}[(a)]
\item How many solutions are there to this, under the restrictions each $x_i$ is a natural number.
\item How many solutions, under the restriction each $x_i$ is a positive integer?
\item Home many solutions, under the restictions that each $x_i$ is natural, except for $x_1$ which is an integer $\geq -3$
\end{enumerate}
\end{quote}
\end{prob}
\section{Counting Proofs}
This section is intended to be completed Thursday June 22nd.
\begin{prob}
Prove by counting in both ways
\begin{quote}
\begin{enumerate}[(a)]
\item $n^2 = n + n(n-1)$
\item $n^3 = n + {n\choose 2}n(n-1) + n(n-1)(n-2)$
\end{enumerate}
\end{quote}
\end{prob}
\begin{prob}
Prove that
\[
n(n-1) {n-2 \choose k} = {n \choose k+2} (k+2)(k+1)
\]
\end{prob}
\begin{prob}
Prove that
\[
{n\choose 3} = \sum_{i=2}^{n-1} (i-1)(n-i)
\]
\end{prob}
\end{document}