\documentclass[10pt]{article} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb}
%\input{preface}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}


\date{Spring 2016}


\begin{document} 
\begin{center}
{\bf Math 432 -- Combinatorics\\
Homework 2}\\
Due  Feb 5, 2016.
\end{center}

Solve the following problems. Show all your work. Each problem is 4 points.\\



\begin{enumerate}
\item Let $p$ be a prime number.    Prove that $p|{p\choose k}$ for integer $k$ with $1\le k\le p-1$.  Use this to prove that $(1+x)^p\equiv 1+x^p \mod p$. \\

\item Count the positive integer solutions to $\sum_{i=1}^n x_i\le k$.\\

\item Count  $4$-words formed from the letters of COMBINATORICS. \\

\item Let $A=\begin{pmatrix} 0& 1\\ 1 & 1\end{pmatrix}$.  Show that $A^{n+1}=\begin{pmatrix} F_{n-1} &  F_n\\ F_{n} & F_{n+1}\end{pmatrix}$ for $n\ge 1$, where $F_n$ is the $n$-th Fibonacci number.  \\

\item  Let $D_n$ be the number of permutations of $[n]$ whose square is the identity permutation.  Prove that $D_n=D_{n-1}+(n-1)D_{n-2}$ for $n\ge 3$ and $D_1=1, D_2=2$.  \\

\item  Problems on Catalan number.   Let $C_n$ be the $n$-th Catalan number. 

\begin{enumerate}
\item  A ballot path of length $2n$ is lattice path from $(0,0)$ to $(n,n)$ that never rises above
$y=x$.   Show that there are $C_n$ ballot paths of length $2n$.   

\item A ballot list of length $2n$ is a list of $n$ 1s and $n$ 0s
such that every initial segment has at least as many 1s as 0s.   Show that there are $C_n$ ballot lists of length $2n$.  
\end{enumerate}
\end{enumerate}

\end{document}


