\documentclass[10pt]{article}
\usepackage[margin=1in]{geometry}
\usepackage[small]{titlesec}
\usepackage{palatino, mathpazo}
\usepackage{inconsolata}
\usepackage{amsmath, amssymb}
\usepackage{enumitem}
\usepackage{graphicx}
\usepackage[normalem]{ulem}
\usepackage{tikz}
\usepackage{wasysym}
\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 2022\\[10pt]
due Friday, March 25, \underline{by the beginning of class}\\[10pt]
}
\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{Mathematical Writing:} An important component of this course is learning how to write mathematics correctly and concisely. Your goal should always be the convince the reader that you are correct! That means explaining your thinking and each step in your solution. I expect you to do the following: explain your reasoning, don't leave out steps, and use full sentences with correct spelling and grammar (including your use of math symbols).
\textbf{\underline{All answers must be fully justified to receive credit.} Answers without justification will not be considered correct.}
\begin{enumerate}
\item A basketball team has $12$ players. However, only five players play at any given time during the game.
\begin{enumerate}
\item In how many ways may the coach choose the five players.
\item To be more realistic, the five players playing a game normally consist of two guards, two forwards, and one center. If there are five guards, four forwards, and three centers on the team, in how many ways can the coach choose two guards, two forwards, and one center?
\end{enumerate}
\item Explain why
\[
\sum_{i=0}^k {m \choose i}{n \choose k-i} = {m+n \choose k}.
\]
\item Use the previous exercise to prove that $\ds{2n \choose n} = \sum_{j=0}^n {n \choose j}^2$.
\item A \emph{labeled graph} consists of a set $V$ of vertices (sometimes called nodes) and a set $E$ of edges between the vertices. An example labeled graph is shown below:
\begin{center}
\begin{tikzpicture}
\draw[fill] (0,0.5) circle (3pt) node[above=3pt] {$A$};
\draw[fill] (-1,0) circle (3pt) node[left=3pt] {$B$};
\draw[fill] (1,0) circle (3pt) node[right=3pt] {$C$};
\draw[fill] (0,-0.5) circle (3pt) node[below=3pt] {$D$};
\draw[thick] (0,-0.5) -- (0, 0.5)--(1,0);
\end{tikzpicture}
\end{center}
The example above has $V = \{A,B,C,D\}$. The edge set $E$ contains 2-subsets of vertices that represent connections between the vertices. In the example above $E = \{\{A,C\}, \{A,D\}\}$.
\begin{enumerate}
\item Draw all eight possible labeled graphs with vertex set $V = \{A, B, C\}$.
\item If a labeled graph has vertex set $V = \{A, B, C, D, E\}$, what is the most possible edges that the graph can have?
\item If a labeled graph has $n$ vertices, what is the most possible edges that it can have?
\item How many different labeled graphs can be drawn with $n$ vertices, with any combination of edges?
\end{enumerate}
\item Suppose you have $100$ distinct marbles (each a different color), and you want to distribute them to 20 different children, 5 marbles per child. (The children are considered distinct!) How many ways are there to do this? Find an answer only in terms of binomial coefficients only. (Note: an overcounting argument would give the answer $(100!)/(5!)^{20}$. Can you show that your answer is equivalent to this?)
\item Think about question 7b from Homework 1 about distributing distinct pieces of candy to five kids. In this question we will try to find an answer using the concept of combinations and binomial coefficients.
The solution to the question with five children and five distinct pieces of candy can be written as
\[
{5 \choose 0}^20! + {5 \choose 1}^21! + {5 \choose 2}^22! + {5 \choose 3}^23! + {5 \choose 4}^24! + {5 \choose 5}^25! = \sum_{i=0}^5 {5 \choose i}^2i!.
\]
In general, if there are $n$ children and $n$ distinct pieces of candy, the solution can be written as
\[
\sum_{i=0}^n {n \choose i}^2i!.
\]
Explain why this formula is correct. (In other words, devise a multi-step process to distribute the candy, possibly involving overcounting, that gives you this as the correct answer.) Your explanation should be \textbf{combinatorial}, involving arguments about how to count things, not \textbf{algebraic} (not just manipulating formulas). \emph{Hint:} Think about each term in the sum as a separate case, and then use the sum principle to combine those cases.
\item This morning I want a coffee from Starfolks (indicated with a star on the map below), and a bagel from the bakery (indicated with an X).
\begin{center}
\begin{tikzpicture}
\foreach \i in {0, 1, ..., 9}{
\foreach \j in {0, 1, ..., 6}{
\draw[fill] (\i, \j) circle (2pt);
}
}
\foreach \i in {0, 1, ..., 9}{
\foreach \j in {0, 1, ..., 5}{
\draw[fill] (\i, \j+0.15)--(\i,\j+0.85);
}
}
\foreach \i in {0, 1, ..., 8}{
\foreach \j in {0, 1, ..., 6}{
\draw[fill] (\i+0.15, \j)--(\i+0.85,\j);
}
}
\node[fill=white] at (0,0) {\Large $\smiley$};
\node[fill=white] at (3,3) {\fbox{\Large $\star$}};
\node[fill=white] at (9,6) {\fbox{X}};
\end{tikzpicture}
\end{center}
If I only follow the grid of streets and walk the minimum total distance (e.g., six blocks to Starfolks and seven blocks from Starfolks to the bakery), how many ways can I:
\begin{enumerate}
\item Walk from home to Starfolks?
\item Walk from home to the bakery (whether or not I stop at Starfolks)?
\item Walk from Starfolks to the bakery?
\item Walk from home to the bakery, after first stopping for coffee at Starfolks?
\item Make a round trip: home to Starfolks, Starfolks to bakery, then bakery back home?
\end{enumerate}
\end{enumerate}
\end{document}