\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\mc[2]%
{\mathchoice{\left(\kern-0.5em{\binom{#1}{#2}}\kern-0.5em\right)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}
{\bigl(\kern-0.3em{\binom{#1}{#2}}\kern-0.3em\bigr)}}
\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 5}
\author{
Spring 2024\\[10pt]
assigned Wednesday, April 3\\
due Wednesday, April 17, \underline{by the beginning of class}\\[5pt]
}
\date{}
\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 (2.4) Find a formula for $P(n,n-4)$ for $n \geq 5$.
\item (2.4) Let $P(n)$ denote the number of integer partitions into any number of parts. Some initial values are
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
$P(n)$ & 1 & 2 & 3 & 5 & 7 & 11 & 15 & 22 & 30 & 42 \\
\hline
\end{tabular}
\end{center}
Find and prove a formula in terms of $P(n)$ for the number of integer partitions of $n$ that have no parts of size $1$.
\item (2.4) In class on Wednesday, March 27, we began to prove a bijection that was going to prove the identity
\[
P(n,k) = P(n-k, 0) + P(n-k,1) + P(n-k,2) + \cdots + P(n-k,k).
\]
We came up with the function $D : A \to B$ that subtracts $1$ from each part and deleting any resulting $0$s. Using type vector notation:
\[
D([1^{p_1}2^{p_2}\cdots m^{p_m}]) = [1^{p_2}2^{p_3} \cdots (m-1)^{p_m}].
\]
The domain $A$ is integer partitions of $n$ into $k$ parts. The codomain $B$ is integer partitions of $n-k$ into \underline{at most} $k$ parts. In class we proved this function is well-defined.
In this exercise, prove that the function is injective. I recommend assuming $p, q \in A$ with $D(p) = D(q)$ and then proving $p=q$. (We started this in class.) Use type vector notation in your proof so that it is clear and precise.
\item (2.4) Prove that the function $D$ in the previous exercise is surjective. Again, use type vector notation and mathematical logic as much as possible.
\emph{Hint:} Let $r \in B$, so $r$ is an integer partition of $n-k$ into $j$ parts where $0 \leq j \leq k$. Write $r$ in type vector notation. Find a partition $p \in A$ with the property that $D(p) = r$. Make sure to prove that the $p$ you find really is in $A$!
\item (3.1) How many functions $[6] \to [7]$ have at most two arrows pointing to each element of the codomain?
\item (3.1) Derive an identity for $\ds{n \choose k}$ via inclusion-exclusion by counting the $k$-multisets of $[n]$ in which each element of $[n]$ appears at most once. Use $p_i = ``\text{element $i$ appears more than once in the multiset}''$ as the $i$th property, for $1 \leq i \leq n$.
\item (3.1) A taxi drives from the intersection labeled $A$ to the intersection labeled $B$ in the grid of streets shown below. The driver only drives north (up) or east (right.)
\begin{center}
\begin{tikzpicture}[scale=0.5]
\draw (0,0) grid (10,6);
\draw[fill] (0,0) circle (6pt) node[left=3pt] {$A$};
\draw[fill] (10,6) circle (6pt) node[right=3pt] {$B$};
\draw[fill=white] (2,3) circle (6pt);
\draw[fill=white] (4,1) circle (6pt);
\draw[fill=white] (7,2) circle (6pt);
\draw[fill=white] (8,5) circle (6pt);
\end{tikzpicture}
\end{center}
Traffic reports indicate that there is a heavy congestion at the intersections identified. How many routes from $A$ to $B$ can the driver take that avoid all congested intersections? Your answer should use the idea of inclusion-exclusion.
\item See the graph $G$ in Figure 5.46 on page 102 (in Section 5.9, Exercises) of the free textbook ``Applied Combinatorics'' by Keller and Trotter. Write $G$ formally as a set $V$ of vertices and $E$ of edges. Then, list the degrees of all of the vertices.
\item Draw a graph with $6$ vertices having degrees $5$, $4$, $4$, $2$, $1$, and $1$ or explain why such a graph does not exist.
\end{enumerate}
\end{document}