\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}
\newcommand{\pointseach}[1]{\hfill {\bf \color{darkgray} [#1 points each]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 9
}

Please submit in class at 8:00am on Friday 4th August
\end{center}

\subsection*{Exercises}

\begin{enumerate}[1.]
\item Let $X$ be a finite set with $|X| = n \ge 1$.
\begin{enumerate}[(a)]
\item Let $a \in X$. Prove that $|X \setminus \{ a \}| = n-1$.
\points{6}

\item Does part (a) remain true if we drop the requirement that $a \in X$? Why or why not?

\points{2}
\end{enumerate}

\item 
\begin{enumerate}[(a)]
\item Count the set of six-card hands from a standard $52$-card deck that contain at least one card of each suit.
\points{4}

\item Fix $n \in \mathbb{N}$ with $n>0$. Prove that the number of surjections $[n] \to [3]$ is $3^n - 3 \cdot 2^n + 3$.

\points{6}
\end{enumerate}

\item Prove by double counting that $\displaystyle \sum_{k=m}^n \binom{n}{k} \binom{k}{m} = 2^{n-m} \binom{n}{m}$, where $m,n$ are fixed natural numbers such that $m \le n$.
\points{4}
\end{enumerate}

\subsection*{Project milestone}

{\color{red} Please submit your work for the project milestone separately from your homework.}

\begin{itemize} \vspace{-10pt}
\item State and prove the main result of your project.
\points{3}
\item Answer the prescribed questions for your project.
\points{6}
\end{itemize}

\subsection*{Optional problems}

Homeworks 9 and 10 will contain additional optional problems totalling $35$ points between them ($14$ points on Homework 9, and $21$ points on Homework 10). You do not need to attempt these problems. If you do, then your score out of $35$ will replace your lowest homework score from Homeworks 1 through 8.

\begin{enumerate}[Opt 1.] \vspace{-10pt}
\item Let $m,n \in \mathbb{N}$. Prove that there is a bijection $[mn] \to [m] \times [n]$.
\points{7}

\item Prove by double counting that $\displaystyle \sum_{i=1}^n \binom{i-1}{2} (n-i) = \binom{n}{4}$ for all $n \in \mathbb{N}$.
\points{7}
\end{enumerate}

\end{document}