  \documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math375}{Homework 6}{Due: Sept 24, 2015}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  \textbf{Show your work}; See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item Suppose that $n$ men and $n$ women attend a meeting.  Let $A$ be the set of all subsets of $n$ people.  (Here, there are no restrictions on gender, so $A$ contains the set of all $n$ men, as well as the set of all $n$ women.)

\begin{enumerate}
	\item Determine $|A|$.
	\item For each $k$ with $0\le k\le n$, let $B_k$ be the set of all subsets with $k$ men and $n-k$ women.  Determine $|B_k|$.
	\item Use parts (a) and (b) to find a simple formula for $\sum_{k=0}^n \binom{n}{k}^2$.  (Hint: apply $\binom{n}{k} = \binom{n}{n-k}$ to one of the two factors in $\binom{n}{k}^2$.)
\end{enumerate}

\item A \emph{bitstring} is an ordered list of zeros and ones; for example, 0110 and 10100 are bitstrings of lengths 4 and 5, respectively.  As a special case, we use $\varepsilon$ to denote the empty bitstring, which has length 0.
	\begin{enumerate}
		\item Show that the set of all bitstrings of finite length is countable.
		\item Is the set of all bitstrings of infinite length countable?  Justify your answer.
	\end{enumerate}
	
\item Is $\N \times \N \times \N$ (the set of all $3$-tuples $(x,y,z)$ with non-negative integer values) countable?  Justify your answer.

\end{enumerate}

\end{document}
