\documentclass[12pt]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\providecommand{\abs}[1]{\lvert#1\rvert}
\providecommand{\norm}[1]{\lVert#1\rVert}

\newtheorem{thm}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{fact}[thm]{Fact}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{eg}{Example}
\newtheorem{ex}{Exercise}
\newtheorem{defi}{Definition}
\newtheorem{hw}{Problem}
\newenvironment{sol}
  {\par\vspace{3mm}\noindent{\it Solution}.}
  {\qed}

\newcommand{\ov}{\overline}
\newcommand{\cb}{{\cal B}}
\newcommand{\cc}{{\cal C}}
\newcommand{\cd}{{\cal D}}
\newcommand{\ce}{{\cal E}}
\newcommand{\cf}{{\cal F}}
\newcommand{\ch}{{\cal H}}
\newcommand{\cl}{{\cal L}}
\newcommand{\cm}{{\cal M}}
\newcommand{\cp}{{\cal P}}
\newcommand{\cz}{{\cal Z}}
\newcommand{\eps}{\varepsilon}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\dist}{\mbox{\rm dist}}
\newcommand{\bn}{{\mathbf N}}
\newcommand{\bz}{{\mathbf Z}}

\setlength{\parindent}{0pt}
%\setlength{\parskip}{2ex}
\newenvironment{proofof}[1]{\bigskip\noindent{\itshape #1. }}{\hfill$\Box$\medskip}

\begin{document}

$\;$\hfill Due: 2011/09/19 before class

\begin{center}
{\LARGE\bf Homework 1}
\end{center}

\begin{hw}
Calculate the following: \\
(a) $\binom{10}{8}$; \\
(b) The inverse of $1, 2, 3, 4, 5, 6$ in $\bz_7$, i.e. for each $1 \leq i \leq 6$, find $j = i^{-1}$ such that $i j \equiv 1 \mod 7$; \\
(c) The rightmost digit in the decimal $\binom{449}{137}$, i.e. $\binom{449}{137} \mod 10$.
\end{hw}

\begin{hw}
Find the number of ordered pairs $(A, B)$ such that $A, B \subseteq [n]$ and $A \cap B = \emptyset$.
\end{hw}

\begin{hw}
Prove
\[\sum_{r=0}^n r^2 \binom{n}{r} = n(n+1) 2^{n-2}.\]
For extra challenge, find a combinatorial proof.
\end{hw}

\begin{hw}
Give a combinatorial proof for
\[
\sum_{k=0}^n \binom{2k}{k} \binom{2n-2k}{n-k} = 4^n.
\]
\end{hw}

\end{document}
