\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{cjhebrew}
\usepackage{substr}

\IfSubStringInString{\detokenize{solution}}{\jobname}{%
  % Solutions
  \newcommand\qfill{}
  \newcommand\qpage{}
  \newcommand\qonly[1]{}
  \newcommand\answer[1]{#1}
  \newcommand\question[1]{{\em #1}}
  \newcommand\rubric[1]{}
}
{%
  \newcommand\qfill{\vfill}
  \newcommand\qpage{\newpage}
  \newcommand\qonly[1]{#1}
  \newcommand\answer[1]{}
  \newcommand\question[1]{#1}
  \newcommand\rubric[1]{}
}

\pagestyle{fancy}
\lhead{MATH 387-01}
\chead{Problem Set \#2\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due September 21, 2015}}

\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{Prove that for every positive
    integer $n$, \[\sum_{k=0}^n\binom
    nk^2=\sum_{\ell=0}^n\sum_{r=0}^{\lfloor\frac{n-\ell}2\rfloor}\binom
    n\ell\binom{n-\ell}r\binom{n-\ell-r}r.\]
    For example: 
    \begin{multline*}
      \binom30^2+\binom31^2+\binom32^2+\binom33^2=20=\\
      \binom 30\binom 30\binom 30+\binom 30\binom31\binom 21+\binom 31\binom20\binom20+\binom31\binom 21\binom11+\binom32\binom10\binom10+\binom33\binom00\binom00
    \end{multline*}
    (Hint: you probably want to prove this combinatorially: the left
    side can be thought of as enumerating pairs of subsets of
    $\{1,2,\ldots,n\}$ with a particular property. Can you
    characterize each pair in other ways, and count those
    characterizations?)}

  \answer{}

\item {\bf (10 points)} \question{Prove combinatorially that for
    positive integers $m$, $w$, and $k$, $\sum_{j=0}^k\binom mj\binom
    w{k-j}=\binom{m+w}k$. (Hint: determine what the right side counts,
    and then divide those objects into $k+1$ classes whose sizes are
    on the left, based on their properties.}

  \answer{}

\item {\bf (10 points)} \question{Suppose that a teacher wishes to
    distribute 25 identical pencils to Ahmed, Barbara, Casper, and
    Dieter such that Ahmed and Dieter receive at least one pencil
    each, Casper receives no more than five pencils, and Barbara
    receives at least four pencils. In how many ways can such a
    distribution be made?}

  \answer{}

\item {\bf (10 points)} \question{The Catalan number $C_n$ enumerates,
    among other things, the number of ways to nest $n$ pairs of
    parentheses, the number of ways to build a binary tree with $n$
    nodes, the number of Dyck paths from $(0,0)$ to $(0,2n)$, and the
    number of ways to build a binary tree where each node with
    children has 2 children, and which has $n+1$ leaves.

    Show with an \emph{explicit bijection} to one of the structures
    described above, that the triangulations by noncrossing diagonals
    of a convex $(n+2)$-gon are also enumerated by $C_n$. For
    instance, $C_4=14$, and below are the 14 triangulations of a
    hexagon:}
  \begin{center}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(120:1)--(240:1)--cycle;
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(180:1)--(300:1)--cycle;
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(120:1)--(300:1)--(180:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(180:1)--(0:1)--(240:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(240:1)--(60:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(240:1)--(60:1)--(180:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(300:1)--(120:1)--(240:1);
    \end{tikzpicture}\\
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(0:1)--(180:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (0:1)--(60:1);
      \draw (0:1)--(120:1);
      \draw (0:1)--(180:1);
      \draw (0:1)--(240:1);
      \draw (0:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (60:1)--(0:1);
      \draw (60:1)--(120:1);
      \draw (60:1)--(180:1);
      \draw (60:1)--(240:1);
      \draw (60:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (120:1)--(0:1);
      \draw (120:1)--(60:1);
      \draw (120:1)--(180:1);
      \draw (120:1)--(240:1);
      \draw (120:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (180:1)--(0:1);
      \draw (180:1)--(60:1);
      \draw (180:1)--(120:1);
      \draw (180:1)--(240:1);
      \draw (180:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (240:1)--(0:1);
      \draw (240:1)--(60:1);
      \draw (240:1)--(120:1);
      \draw (240:1)--(180:1);
      \draw (240:1)--(300:1);
    \end{tikzpicture}
    \begin{tikzpicture}[scale=0.6]
      \draw (0:1)--(60:1)--(120:1)--(180:1)--(240:1)--(300:1)--cycle;
      \draw (300:1)--(0:1);
      \draw (300:1)--(60:1);
      \draw (300:1)--(120:1);
      \draw (300:1)--(180:1);
      \draw (300:1)--(240:1);
    \end{tikzpicture}
  \end{center}

  \answer{}

\end{enumerate}

\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      \begin{cjhebrew}
        /sty 'bnyM bwnwt /sny btyM; /sl/s 'bnyM bwnwt /s/sh btyM; 'rb` 'bnyM b
        wnwt 'rb`h w`/sryM btyM; .hm/s 'bnyM bwnwt m'h w`/sryM btyM; /s/s 'bnyM 
bwnwt /s
        b` m'wt w`/sryM btyM; /sb` 'bnyM bwnwt .hm/st 'lpyM w'rb`yM btyM; mk'N w
'ylK .s'
        w.h/swb mh /s'yN hph ykwl ldbr w'yN h'wzN ykwlh l/smw`
      \end{cjhebrew}\\
      \phantom0\hfill---\cjRL{spr hy.syrh pr.S d${}'$ m/snh .t${}''$z}
    \end{minipage}
  }
\end{center}

\end{document}
