
\documentclass[12pt,english]{amsart}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{geometry}
\geometry{verbose,tmargin=.8in,bmargin=1in,lmargin=1in,rmargin=1in}
\usepackage[all]{xy}
\usepackage{bussproofs}
\usepackage{enumitem}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{plain}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{plain}
\newtheorem{example}[theorem]{Example}
\theoremstyle{remark}
\newtheorem{proposition}[theorem]{Proposition}

\newcounter{problems}
\theoremstyle{definition}
\newtheorem{problem}[problems]{Problem}

\theoremstyle{remark}
\newtheorem*{solution}{Solution}


\newcommand{\bR}{\mathbb{R}}
\newcommand{\bC}{\mathbb{C}}
\newcommand{\bQ}{\mathbb{Q}}
\newcommand{\bZ}{\mathbb{Z}}
\newcommand{\bP}{\mathbb{P}}
\newcommand{\bT}{\mathbb{T}}
\newcommand{\bI}{\mathbb{I}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\cB}{\mathcal{B}}
\newcommand{\GL}{\mathrm{GL}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\cM}{\mathcal{M}}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cP}{\mathcal{P}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\ra}{\rightarrow}
\newcommand{\La}{\Longleftarrow}
\newcommand{\inj}{\hookrightarrow}
\newcommand{\Ra}{\Longrightarrow}
\newcommand{\LRa}{\Longleftrightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\id}{\mathrm{id}}

\newcommand{\sC}{\mathscr{C}}
\newcommand{\sG}{\mathscr{G}}
\newcommand{\sN}{\mathscr{N}}
\newcommand{\sI}{\mathscr{I}}
\newcommand{\sL}{\mathscr{L}}
\newcommand{\sU}{\mathscr{U}}
\newcommand{\sF}{\mathscr{F}}
\newcommand{\sD}{\mathscr{D}}
\newcommand{\sK}{\mathscr{K}}
\newcommand{\sV}{\mathscr{V}}
\newcommand{\sO}{\mathscr{O}}
\newcommand{\sS}{\mathscr{S}}
\newcommand{\sP}{\mathscr{P}}




\title{Math 301: Homework 8}



\begin{document}
\maketitle


\begin{problem}
	Let $n,k \in \bN$ with $k\leq n$. Find a bijection between ${[n] \choose k}$ and $[n]\choose {n-k}$ to deduce that ${n \choose k}={n \choose {n-k}}$.
	\end{problem}

\begin{problem} Use double counting to prove that 
	$$\sum_{k=0}^n {n\choose k}^2={2n \choose n}$$
	for all $n\in \bN$.
	
	\end{problem}

\begin{problem}
	Use the pigeonhole principle to show that given 100 integers, one can choose 15 of them such that the difference of any two is divisible by 7.
	\end{problem}

\begin{problem} For $X$ a finite set and $m_1,m_2,\dots, m_k \in \bN$, denote by $X \choose {m_1 \ m_2 \  \dots \ m_k}$ the set of $k$-tuples $(U_1,\dots,U_k)$ of pair-wise disjoint subsets of $X$ with $|U_i|=m_i$. Let $n,k,m_1,\dots, m_k\in \bN$ be integers. Show that
	$$\left | [n] \choose {m_1 \ m_2 \  \dots \ m_k} \right | = \begin{cases} 0 &  m_1+\dots + m_k >n \\
	\frac{n!}{m_1!\cdot m_2! \cdot \dots \cdot m_k! \cdot (n-m_1-m_2 -\dots - m_k)!} & \text{otherwise}
		\end{cases}$$


	
\end{problem}


\begin{problem} $\ $
	\begin{enumerate}[label=\alph*)]
		\item Find the number of surjective maps from $[5]$ to $[4]$.
		\item 	Find the number of injective maps from $[3]$ to $[4]$.
	\end{enumerate}
	
\end{problem}



\begin{problem}
	How many natural numbers less than 100 are multiples of 2, 3 or 5?	
\end{problem}

\begin{problem} $ \ $
	\begin{enumerate}[label =\alph*)]
		\item Let $n\in \bN$. Show that the set of subsets of $\bN$ of size $n$ is countable.
		\item Show that the set of finite subsets of $\bN$ is countable.
		\end{enumerate}



\end{problem}

\begin{problem}
	Consider the set $X$ of all subset $U\subset \bN$ such that neither $U$ nor $\bN \setminus U$ is finite. Show that $X$ is uncountable.
\end{problem}	


\end{document}
