\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}

\newcommand{\inv}[1]{#1^{-1}}

\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 28 March 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).
\begin{enumerate}

\item Prove Claims 1 and 2 in the proof of Lemma 1 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Finite%20Cardinality.pdf}{Finite Cardinality Notes}.

\item (*) Prove Corollary 4 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Finite%20Cardinality.pdf}{Finite Cardinality Notes}.

\item Let $X$ be a finite set. Let $\mathcal{S}$ be the subset of $\mathcal{P}(X)$ defined by
\[\mathcal{S} =\{A\in\mathcal{P}(X)\ | \ |A|\hbox{ is odd}\}.\]
Prove that $|\mathcal{S}| = |\mathcal{P}(X)\ba\mathcal{S}|$.

\item Prove that if $X$ is a finite set, and $S\subseteq X$ with $S\neq X$, then $|S|<|X|$.

\item Let $B\subseteq A$, where $|A|=n$ and $|B|=k$. Let $\mathcal{S}$ be the subset of $\mathcal{P}(A)$ defined by
\[\mathcal{S}=\{C\in\mathcal{P}(A)\ | \ |C\cap B|=1.\}\]
Determine $|\mathcal{S}|$. Prove that your answer is correct.

\item (*) Prove the Binomial Theorem (Theorem 5 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Combinatorics.pdf}{Combinatorics Notes}).

\item Prove that $\displaystyle\sum_{k=1}^n (-1)^k{n\choose k} = -1$.

\item (*) Let $X=\{a,b, c, d, \dots, x, y, z\}$, the letters in the standard English alphabet. We say a permutation of $X$ {\it contains a string} if the letters of the string appear, consecutively, in that order in the permutation.

For example, the permutation $qwertyuiopasdfghjklzxcvbnm$ contains the string $wert$, but it does not contain the string $wet$.

How many permutations of $X$ do NOT contain any of the strings $fish$, $mouse$, or $cat$?
\item How many positive integers less than 1000 are not divisible by 5, 7, or 12?

\item (*) The World Series in baseball is a series of up to 7 games. Once one team has won 4 games, the series ends. 

Suppose teams A and B are playing in the world series. How many ways can A win? For example, A could win by winning games 1, 3, 4, and 5. At this point the tournament would end, so no winner would be determined for games 6 or 7.


\item You go to a party with $n-1$ of your friends (so there are $n$ total people). All of you check your coat with the coat check guy. Unfortunately, the coat check guy parties a little too hard, and loses all the tags, so when you leave, he just gives you whatever coat he grabs. 

\begin{enumerate}
\item How many ways can the coat check guy distribute the coats where you get your own coat back?

(Reinterpreted: the coats are given back in a permutation. You are looking for how many permutations keep one particular coat in one particular place)

\item You and your friend Tim both want to get your own coats back. How many ways does this happen?

\item Suppose you have $k-1$ roommates. How many ways can the coats be distributed so that your house of $k$ people goes home with the right $k$ coats, in some order?

\item Suppose you have $k-1$ roommates. How many ways can the coats be distributed so that your house of $k$ people goes home with the right $k$ coats, in the right order?
\end{enumerate}

\item Prove that for all $n\in\N$,
\[{2n\choose n} = \sum_{k=0}^n{n\choose k}^2.\]
Recommended strategy: counting in 2 ways.

\item (*) Let $n, m\in\N$, with $m\leq n$. Prove that
\[\sum_{k=m}^n {n\choose k}{k\choose m} = 2^{n-m}{n\choose m}.\]
Recommended strategy: counting in two ways.



\end{enumerate}
\end{document}