\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}
\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 2}
\author{
Spring 2024\\[10pt]
assigned Friday, February 9\\
due \underline{Wednesday}, February 21, \underline{by the beginning of class}\\[5pt]
}
\date{This homework covers the material from Sections 1.1 - 1.3.}
\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 to 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
% \begin{enumerate}
% \item What is the size of the set $[n] \times [n]$?
% \item What is the size of the set $\{(a,b) \in [n] \times [n] : a \neq b\}$?
% \item What is the size of the set $\{(a,b,c) \in [n] \times [n] \times [n] : a \neq b, a \neq c, b \neq c\}$?
% \end{enumerate}
\item Let $S = \{1,2,3,4,5,6\}$ and let $T = \{(i,j) \in \Z \times \Z : 1 \leq i \leq j \leq 6\}$ (i.e., $T$ is the ordered pairs from $S \times S$ with the property that the second item is at least as big as the first).
\begin{enumerate}
\item How is the set $S \times S$ related to rolling a pair of dice? What is $|S \times S|$?
\item How is the set $T$ related to rolling a pair of dice? What is $|T|$?
\item What circumstances would lead you to prefer to use $S \times S$ versus $T$ to model rolling two dice?
\end{enumerate}
\item Let $A$ and $B$ be finite sets and define $a = |A|$ and $b=|B|$. How many injective (i.e., one-to-one) functions are there with domain $A$ and codomain $B$?
\item Let $A$, $B$, and $C$ be finite sets and define $a = |A|$, $b=|B|$, and $c = |C|$. How many functions are there with domain $A \times B$ and codomain $C$?
\item Let $n$ be a positive integer. Let $|A| = 2n$ and $|B| = n$. Let's call a function $f : A \to B$ ``doubley'' if it has the property that for every element $b \in B$, there are exactly two distinct elements $a_1, a_2 \in A$ such that $f(a_1) = b$ and $f(a_2) = b$. (Less formally, every element of the output is pointed to by exactly two input elements.) How many doubley functions are there?
\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 Let $A$ and $B$ be finite sets that are the same size. Prove that a function $f$ with domain $A$ and codomain $B$ is injective (one-to-one) if and only if it is surjective (onto). (Don't forget that ``if and only if'' means you need to prove the the theorem in both directions: (1) if $f$ is injective then it is surjective, and (2) if $f$ is surjective then it is injective.)
\item Prove that if $f: A \to B$ and $g : B \to C$ are both surjective, then $g \circ f$ is surjective.
\item If there are 15 Marquette (MU) students and 6 UW-Milwaukee (UWM) students, how many ways are there to:
\begin{enumerate}
\item create a group that has an equal number of MU students and UWM students?
\item create a group that at least one MU student and at least one UWM student?
\item create a group with 10 students that also has an odd number of UWM students?
\end{enumerate}
\item One Homework 1, I asked you (essentially) the following question:
\begin{quotation}
\noindent A tennis club has $2n$ members. Suppose we want to pair up the $2n$ members into $n$ groups of $2$ so that they can play singles matches, and then pick which person out of each group serves first. How many ways are there to do this?
\end{quotation}
I posed this question to ChatGPT three times. On the next piece of paper, you will see its three answers. Your assignment for this problem is to grade its three answers on the E/M/P/I scale. Decide which answer(s) are correct. Identify which parts of the answers are incorrect, which parts are not adequately explained/justified, etc, just like I would on your assignments.
So that you don't need to rewrite ChatGPT's answers, you should tear off the next paper, grade it by writing on the paper and submit that with the rest of your homework answers.
\pagebreak
\begin{spacing}{1.5}
\textbf{\Large Answer \#1:}
To pair up $2n$ members into $n$ groups of $2$, we can first calculate the number of ways to select the first pair, then the number of ways to select the second pair from the remaining members, and so on.
For the first pair, there are $\ds\binom{2n}{2}$ ways to choose two members out of $2n$. Once the first pair is chosen, there are $(2n - 2)$ members left.
For the second pair, there are $\ds\binom{2n - 2}{2}$ ways to choose two members out of the remaining $(2n - 2)$. Then there are $(2n - 4)$ members left.
Continuing this process, for the $n$th pair, there are $\ds\binom{2}{2}$ ways to choose the final pair.
So, the total number of ways to pair up $2n$ members into $n$ groups of $2$ is:
\[
\binom{2n}{2} \times \binom{2n - 2}{2} \times \binom{2n - 4}{2} \times \ldots \times \binom{2}{2}
\]
This can be simplified using factorials:
\[
\frac{(2n)!}{2^n \cdot n!}
\]
Finally, for each group of $2$, we have $2$ choices for which member serves first. So, the total number of ways to pair up the $2n$ members and pick who serves first is:
\[
2^n \times \frac{(2n)!}{2^n \cdot n!} = \frac{(2n)!}{n!}
\]
Therefore, there are $\ds\frac{(2n)!}{n!}$ ways to pair up the $2n$ members into $n$ groups of $2$ and pick who serves first.
\hrulefill
\textbf{\Large Answer \#2:}
To solve this problem, we can use the concept of combinations.
When pairing up $2n$ members into $n$ groups of $2$, we are essentially forming pairs of players. The number of ways to choose $2$ players out of $2n$ is given by the combination formula, which is $\binom{2n}{2}$.
After forming the pairs, we need to pick one person from each pair to serve first. For each pair, there are $2$ choices for who serves first. Since there are $n$ pairs, the total number of ways to pick one person from each pair to serve first is $2^n$.
Therefore, the total number of ways to pair up the $2n$ members into $n$ groups of $2$ and then pick who serves first is the product of the number of ways to form pairs and the number of ways to pick who serves first:
$$
\text{Total ways} = \binom{2n}{2} \times 2^n
$$
Using the formula for combinations $\ds\binom{2n}{2} = \frac{(2n)!}{2!(2n-2)!} = \frac{(2n)(2n-1)}{2}$, the expression becomes:
$$
\text{Total ways} = \frac{(2n)(2n-1)}{2} \times 2^n
$$
$$
= n(2n-1) \times 2^n
$$
So, there are $n(2n-1) \times 2^n$ ways to pair up the $2n$ members into $n$ groups of $2$ and pick who serves first.
\hrulefill
\textbf{\Large Answer \#3:}
To pair up the $2n$ members into $n$ groups of $2$ for singles matches, we first need to choose $2$ members out of $2n$ for the first group, then $2$ members out of the remaining $2n-2$ for the second group, and so on until we have $n$ groups.
The number of ways to choose $2$ members out of $2n$ for the first group is $\binom{2n}{2}$.
After choosing the first group, we have $2n-2$ members left. The number of ways to choose $2$ members out of these $2n-2$ for the second group is $\binom{2n-2}{2}$.
Continuing this process, the total number of ways to pair up the $2n$ members into $n$ groups of $2$ is given by the product of these combinations:
$$\binom{2n}{2} \times \binom{2n-2}{2} \times \ldots \times \binom{2}{2}.$$
This can be simplified as:
$$\frac{(2n)!}{2^n}.$$
For each pair, we have $2$ options for selecting the player who serves first. Therefore, we need to multiply the above result by $2^n$ to account for the choice of servers for each pair.
Hence, the total number of ways to pair up the $2n$ members into $n$ groups of $2$ and pick the person out of each group who serves first is:
$$\frac{(2n)!}{2^n} \times 2^n = (2n)!.$$
\hrulefill
\end{spacing}
\end{enumerate}
\end{document}