\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 2024\\[10pt]
	assigned Wednesday, January 24\\
	due \underline{Friday}, February 9, \underline{by the beginning of class}\\[5pt]
}
\date{This homework covers the material from Section 1.1.}
\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 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\}$. Recall that if $X$ is a set, then $|X|$ means the number of elements in $X$, also called the ``cardinality of $X$''. Compute the following cardinalities:
	\begin{enumerate}
		\item $|S|$
		\item $|T|$
		\item $|S \cap T|$
		\item $|S \cup T|$
	\end{enumerate}
		
	\item Consider drawing three cards from a standard deck of cards\footnote{A standard deck of cards has 52 cards. Each card has a ``value'' and a ``suit''. There are 13 different values: A(ce), 2, 3, 4, 5, 6, 7, 8, 9, 10, J(ack), Q(ueen), K(ing). There are four different suits: hearts ($\heartsuit$), diamonds ($\diamond$), clubs ($\clubsuit$) and spades ($\spadesuit$). In total there are $4 \cdot 13 = 52$ cards.}. 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. In this question you count the number of ways to distribute the candy to the children under various conditions. You will always assume that the children are considered distinct; for example if Child A gets a blue piece of candy and Child B gets a green piece of candy, that counts as a different distribution than if Child A gets the green piece and Child B gets the blue piece. (As usual, don't try to list all the possibilities, there will be too many! But for brainstorming, you can try simplifying the problem and then listing the possibilities for the simpler version.)
	\begin{enumerate}
		\item How many ways are there to distribute the candy if: the pieces of candy are also considered distinct (they're all different) and each child gets exactly one piece?
		\item How many ways are there to distribute the candy if: the pieces of candy are distinct, but each child can get any number of candies, and assuming all five are distributed? (So, each child can get 0 pieces, 1 piece, or more than 1 piece, but only 5 pieces distributed in total.)
		\item How many ways are there to distribute the candy if: the pieces of candy are considered identical and each child gets exactly one piece?
		\item How many ways are there to distribute the candy if: the pieces of candy are considered identical, but each child can get any number of candies, and assuming all five are distributed (like part (b))?
	\end{enumerate}
	
	
	\item A PIN (personal identification number) is a sequence of four digits used for security purposes by banks 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 $8588$?
	\end{enumerate}
	
	\item A tennis club has $2n$ members.
	\begin{enumerate}
		\item Suppose we want to pair up the $2n$ members into $n$ groups of $2$ so that they can play singles matches. How many ways are there to do this?
		\item Once they've already been paired up, how many ways are there to pick one person from each pair to serve first?
		\item Combining your two previous answers: How many ways are there to start with $2n$ people, pair them up into $n$ groups of $2$, and then pick one person from each pair to serve first?			
	\end{enumerate}
	
	\item There are $100$ students in a gym class. The instructor wants to split them into 5 groups of 20 students each. In how many ways can this be done? As always, starting with smaller examples can help you figure out the right approach. (\emph{Hint:} There are many good ways to solve this. One of them involves intentionally overcounting, and then dividing to account for that.)

	\item \begin{enumerate}
		\item  How many solutions does the equation $a + b + c + d + e + f = 517$ have in which $a, b, c, d, e, f$ are all non-negative integers, $b \geq 5$, and $e \geq 20$?  For example: ($a=200$, $b=100$, $c=150$, $d=27$, $e=20$, $f=160$) is one solution.
		\item How many solutions does the inequality $a + b + c + d + e + f \leq 517$ have in which $a, b, c, d, e, f$ are all non-negative integers, $b \geq 5$, and $e \geq 20$? For example: ($a=25$, $b=11$, $c=200$, $d=0$, $e=20$, $f=77$) is one solution.
	 \end{enumerate}
(\emph{Hint:} Think about using the robot method for both parts, and consider ways to simplify the question first.)
	
	\item
	\begin{enumerate}
		\item How many permutations of $[7]$ have no odd digits adjacent to each other? For example $2714536$ is invalid because $7$ and $1$ are next to each other. (Don't try to list them all, find a way to count.)
		\item How many permutations of $[6]$ have no odd digits adjacent to each other? \emph{Hint:} this one is a bit trickier. 
		\item If $n$ is odd, how many permutations of $[n]$ have no odd digits adjacent to each other?
		\item What makes the following question harder: If $n$ is even, how many permutations of $[n]$ have no odd digits adjacent to each other? You don't need to actually answer the question unless you want a good challenge.
 	\end{enumerate}


		

\end{enumerate}
\end{document}


