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


\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 1}
\author{
	Spring 2022\\[10pt]
	due Wednesday, Februrary 16, \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 Write each of the following sets using set-builder notation, and list five elements from each set.
	\begin{enumerate}
		\item The set $S$ of rational numbers such that the difference between the numerator and the denominator, when written in reduced terms, is even.
		\item The set $R$ of pairs $(a,b)$ of positive integers whose sum is a multiple of $4$.
		\item The set of real numbers whose square is a natural number.
	\end{enumerate}

	\item Let $n$ be a positive integer and define $N = \{1, 2, \ldots, n\}$ to be the set of positive integers from $1$ to $n$. For example, if $n = 4$, then $N = \{1,2,3,4\}$. Each of the following answers should have the variable $n$ in it.
	\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$ and $T$ be two finite sets. Explain why $|S \cup T| + |S \cap T| = |S| + |T|$.

	(This is a great example of a fact that just seems obvious once you write a few examples out. The point of the exercise is to find a clear and precise way of justifying it concretely without requiring any leaps of logic.)
	
	\item Let $S = \{n \in \Z : 1 \leq n \leq 100\}$ and let $T$ denote the set of positive multiples of $3$ with at most three digits, i.e., $T = \{3, 6, 9, \ldots, 999\}$. Compute the following cardinalities:
	\begin{enumerate}
		\item $|S|$
		\item $|T|$
		\item $|S \cap T|$
		\item $|S \cup T|$
	\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 Consider drawing three cards from a standard deck of cards (see Problem 14 on page 22 of the book for a refresher on which cards are in a standard deck). Assume you that you \textbf{do not} return each card to the deck after drawing it. In how many ways can you:
	\begin{enumerate}
		\item Select a 10 in round 1, then a 9 in in round 2, then an 8 in round 3?
		\item Select three cards whose numbers are $\{8, 9, 10\}$ (so, ignoring suits and the order in which they were selected)?
		\item Select three cards that form a run (three consecutive cards of the same suit, where the Ace can be low (like a 1) or high (higher than king)), in order. For example some valid runs are $(A\spadesuit, 2\spadesuit, 3\spadesuit)$, $(10\heartsuit, J\heartsuit, Q\heartsuit)$, and $(Q\clubsuit, K\clubsuit, A\clubsuit)$. It doesn't count as a run if you pick them in the wrong order, like $(10\diamond, 9\diamond, 8\diamond)$, or if they wrap around, like $(K\clubsuit, A\clubsuit, 2\clubsuit)$.
	\end{enumerate}
	
	\item It's Halloween and five children arrive at your door, all hoping for candy. You have exactly five pieces of candy and you can give away none of the candy, or all of the candy, or any amount in between. (So, each child will receive zero pieces, or one piece.)
	\begin{enumerate}
		\item Assume all of the pieces of candy are identical (the children are obviously distinct). How many different ways can you distribute the candy? Try to answer this in a way that doesn't require you to list all the ways out, although this might still be a useful first step in brainstorming.
		\item Assume all five pieces of candy are distinct (as are the children). How many different ways can you distribute the candy? Try to answer this in a way that doesn't require you to list all the ways out, although this might still be a useful first step in brainstorming.
	\end{enumerate}
		
	\item Let $n$ be a positive integer and define $S = \{1, 2, \ldots, n\}$. In terms of $n$, how many subsets does $S$ have? Try to explain your formula with the product principle.

	\item The existence of a bijection between two finite sets implies that their cardinalities are the same. Consider Problem 15 on page 22 of the textbook, which is a suggested homework question. The number of ways of flipping a coin $n$ times and recording the outcome in order is the same answer as Question 8 above. Construct a bijection $f$ from the domain ``subsets of $\{1, 2, \ldots, n\}$'' to ``possible outcomes of flipping a coin $n$ times''. Prove that your function is a bijection by first proving it is an injection, then proving it's a surjection.

\end{enumerate}
\end{document}


