\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{setspace}
\usepackage{tikz}
\newcommand{\ds}{\displaystyle}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.5ex}
\title{\sc Math 4670 / 5670 -- Combinatorics\\Homework 3}
\author{
Spring 2024\\[10pt]
assigned Wednesday, February 21\\
due Wednesday, March 6, \underline{by the beginning of class}\\[5pt]
}
\date{This homework covers the material from Sections 1.3, 1.4, and 2.1.}
\begin{document}
\maketitle
\begin{center}
\emph{This homework assignment was written in \LaTeX{}. You can find the source code on the course website.}
\end{center}
\textbf{\underline{All answers must be fully justified to receive credit.} Answers without justification will not be considered correct.}
{\Huge $\star$} Questions that ask you to ``prove'' something or ask you to ``give a proof'' should be answered with formal mathematical proofs.
\begin{enumerate}
\item Consider the sets $\N = \{1, 2, 3, \ldots\}$ and $\Z = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$. Come up with a bijection \linebreak $f : \N \to \Z$, and prove that your function really is a bijection.
\begin{itemize}
\item Note 1: It may seem like this is a trick question because $\N$ is a proper subset of $\Z$, but it is not a trick question.
\item Note 2: You don't necessarily have to describe your function like $f(n) = [\text{arithmetic expression of $n$}]$. You can use piecewise functions, or words, to define your function, as long as your words are precise and clear enough to tell me how to compute $f$ for any given input.
\end{itemize}
\item The word BOOKKEEPERS and its variants are the only English words that have three double-letter pairs in a row. How many different ways are there to rearrange the letters in BOOKKEEPERS (not necessarily making a real word).
\item How many eight-letter passwords using the letters A-Z are there in which up to one letter is allowed to be used more than once? This means HVCKEWFX and FOWFLQAZ and FBHHHRHT are allowed, but VSSKVRTF and LLLWWWFW are not.
\item Give a combinatorial proof of the identity
\[
{n \choose k} = {n-1 \choose k-1} + {n-2 \choose k-1} + {n-3 \choose k-1} + \cdots + {k \choose k-1} + {k-1 \choose k-1}.
\]
Note that we can use summation notation to write this identity as
\[
{n \choose k} = \sum_{i=k-1}^{n-1} {i \choose k-1}
\]
\item Give a \underline{combinatorial} proof of the identity
\[
4^n = \sum_{k=0}^n {n \choose k}3^k.
\]
\item A ``\emph{composition of $n$}'' is an ordered sum of positive (nonzero) integers that add up to $n$. For example, there are eight compositions of $4$. They are:
\begin{align*}
1 + 1 + 1 + 1 && 3+1 && 1+3 && 2+2\\
1+1+2 && 1 + 2 + 1 && 2 + 1 + 1 && 4
\end{align*}
In general, there are $2^{n-1}$ compositions of $n$. Prove this fact in the following way. Let $C_n$ be the set of compositions of $n$, and let $S_n$ be the set of subsets of $\{1, 2, \ldots, n-1\}$. Devise a bijection $h : C_n \to S_n$, describe it, and prove that it's really a bijection. Then say why this proves that $|C_n| = 2^{n-1}$. For the sake of concreteness, when you describe your bijection tell me, as an example, which subset it maps the composition $3+7+1+3+1$ to in the case $n=15$.
\item \begin{enumerate}
\item You are at a street corner in a city with a perfectly square grid of roads. You want to go to the coffee shop that is 4 blocks north and 7 blocks east, and you want to do this by only traveling north or east, never going south or west. The picture below shows one possible route. How many possible routes are there?
\begin{center}
\begin{tikzpicture}
\draw[help lines] (-0.5, -0.5) grid (7.5, 4.5);
\draw[fill] (0,0) circle (4pt);
\draw[thick, <-] (-0.2, 0.2) -- (-1, 1) node[above] {you};
\draw[fill] (7,4) circle (4pt);
\draw[thick, <-] (7.2, 3.8) -- (8,3) node[below] {coffee};
\draw[ultra thick] (0,0) -- (0,1) -- (3,1) -- (3,3) -- (6,3) -- (6,4) -- (7,4);
\draw[fill] (0,1) circle (2.5pt);
\draw[fill] (1,1) circle (2.5pt);
\draw[fill] (2,1) circle (2.5pt);
\draw[fill] (3,1) circle (2.5pt);
\draw[fill] (3,2) circle (2.5pt);
\draw[fill] (3,3) circle (2.5pt);
\draw[fill] (4,3) circle (2.5pt);
\draw[fill] (5,3) circle (2.5pt);
\draw[fill] (6,3) circle (2.5pt);
\draw[fill] (6,4) circle (2.5pt);
\end{tikzpicture}
\end{center}
\item If the coffee shop is $n$ blocks north and $m$ blocks east, now how many routes are there?
\end{enumerate}
\item Let $P_{m,n}$ be the set of paths from $(0,0)$ to $(m,n)$. (The previous question asks about $P_{7,4}$ in (a) and $P_{m,n}$ in (b).) Let $S_{m,n}$ be the set of committees of size $m$ picked from a group of $n + m$ people. Figure out a bijection from $P_{m,n}$ to $S_{m,n}$, describe it, and prove that it's a bijection. For the sake of concreteness, when you describe your bijection tell me, as an example, where it maps the path shown in the above picture to for the case $m=7$, $n=4$.
\end{enumerate}
\end{document}