\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}


\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 2022\\[10pt]
	due Wednesday, March 2, \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 Consider all possible subsets of $\{1,2,3\}$.
	\begin{enumerate}
		\item How many unordered pairs of distinct subsets (i.e., $\{A, B\}$ with $A \neq B$) are there?
	\end{enumerate}
	Now, among these pairs of distinct subsets, how many are there with the following properties? \emph{Focus on finding a way to list the appropriate pairs that will help you make sure you don't miss any and don't have duplicates! Think about the ``organizing data'' section of the textbook.}
	\begin{enumerate}[resume]
		\item $A \cup B = \{1,2,3\}$
		\item $A \cap B = \{\}$
		\item $A \cap B = \{3\}$
		\item $|A \cap B| = 1$
	\end{enumerate}

	
	\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 Suppose you go to the grocery store to buy some ice cream, and they have twelve different flavors. In how many ways can you choose three pints to buy if the pints do not have to be different flavors, and the order you choose the pints doesn't matter?
	
	\item 
		\begin{enumerate}
			\item Suppose that every person has 1 cell phone with its own phone number. Define a function that models this information. Clearly state the domain and the codomain, and what the mapping is between input elements and output elements. Then answer whether this function is injective, whether it's surjective, and whether it's bijective.
			\item Suppose every Marquette student takes five courses this semester. Define a function that models this information. Clearly state the domain and the codomain, and what the mapping is between input elements and output elements. Then answer whether this function is injective, whether it's surjective, and whether it's bijective.
		\end{enumerate}
	
	\item A PIN (personal identification number) is a sequence of four digits used for security purposes by banks and order organizations to protect consumer information. Each digit is typically $0$ to $9$. For example, $0394$ is a PIN.
	\begin{enumerate}
		\item How many PINs are there that have only two different digits, each repeated twice, like $1313$ and $8558$?
		\item How many PINs are there that have only two different digits, one repeated three times and once used only once, like $1333$ and $8885$?
	\end{enumerate}
	
	\item A tennis club has $2n$ members. Suppose that we want to pair up the members into groups of two to play singles matches, and then for each pair we want to pick who will serve the ball first? How many ways are there to do this?
	
	\item Another tennis problem! Suppose there are $4n$ people, and you are asked to group them up for doubles games. A doubles game consist of four people, two on one team, and two on another team. How many ways can you group $4n$ people into doubles games? (The order of a pair of people on the same team doesn't matter. The order of the two pairs who play against each other doesn't matter. The order of the doubles games doesn't matter.)

	\item There are $100$ students in a gym class. The instructor wants to split them into 5 groups of 20 students each.
	\begin{enumerate}
		\item In how many ways can this be done?
		\item If the instructor also wants to pick one student from each group to be team captain, and a second (different) student from each group to be assistant captain, how many ways can this whole process be done?
	\end{enumerate}
	
	\item Recall from Lecture 3 about $k$-permutations that $P(n,k)$ is defined to be the number of $k$-permutations of a set with $n$ elements. Give both an algebraic and a combinatorial proof of the identity $P(n,k) = P(n-1,k) + kP(n-1,k-1)$.

	\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 $k$-permutations.
	
		The solution to the question with five children and five distinct pieces of candy can be written as
		\[
			\frac{P(5,0)^2}{0!} + \frac{P(5,1)^2}{1!} + \frac{P(5,2)^2}{2!} + \frac{P(5,3)^2}{3!} + \frac{P(5,4)^2}{4!} + \frac{P(5,5)^2}{5!} = \sum_{i=0}^5 \frac{P(5,i)^2}{i!}.
		\]
		
		In general, if there are $n$ children and $n$ distinct pieces of candy, the solution can be written as
		\[
			\sum_{i=0}^n \frac{P(n,i)^2}{i!}.
		\]
		
		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.) \emph{Hint:} Think about each term in the sum as a separate case, and then use the sum principle to combine those cases.



\end{enumerate}
\end{document}


