\include{preamble}
\usepackage{tikz}

\begin{document}

Math 188, Spring 2021

Homework 3

Due: April 23, 2021 11:59PM via Gradescope

~

Solutions must be {\bf clearly} presented. Incoherent or unclear solutions will lose points. 
\begin{enumerate}

\item
  \begin{enumerate}
  \item Let $a,b$ be rational numbers. Show that any non-negative integer $n$, we have
    \[
      \binom{a+b}{n} = \sum_{i=0}^n \binom{a}{i} \binom{b}{n-i}.
    \]
  \item When $a,b$ are positive integers, give a {\it combinatorial interpretation} of this identity, i.e., describe a set whose size can be interpreted as either expression.
  \end{enumerate}

  
\item How many ways can we arrange the letters of:
  ALGEBRAICCOMBINATORICS\ ?

\item Let $f(n) = \sum_{k=0}^d f_k n^k$ be a degree $d$ polynomial with rational coefficients such that $f(a)$ is an integer for all non-negative integers $a$. (The $f_k$ don't have to be integers for this to be true, for example $f(n) = n(n-1)/2$ has this property.)

\begin{enumerate}
\item Show that there exist {\bf integers} $g_0,\dots,g_d$ such that
  \[
    f(n) = \sum_{k=0}^d g_k \binom{d+n-k}{d}.
  \]

\item Show that the $g_k$ are the coefficients of the numerator of $\sum_{n \ge 0} f(n) x^n$ when expressed as a rational function.

\item Express $\sum_{n \ge 0} (n^4 - 3n^3 + 1) x^n$ as a rational function.
\end{enumerate}

\item Let $n$ be a positive integer. Show that the following are given by the Catalan number $C_n$:
  \begin{enumerate}
  \item the number of $2\times n$ ``increasing'' matrices; a $2 \times n$ matrix is {\bf increasing} if its entries are
  \begin{itemize}
  \item $1,2,\dots,2n$, each appearing exactly once,
  \item increase in each row going from left to right and,
  \item for each column, the bottom entry is larger than the top entry.
  \end{itemize}
  When $n=3$, here are the increasing matrices:
  \begin{align*}
    \begin{bmatrix} 1&2&3\\4&5&6 \end{bmatrix} \qquad
    \begin{bmatrix} 1&2&4\\3&5&6 \end{bmatrix} \qquad
     \begin{bmatrix} 1&2&5\\3&4&6 \end{bmatrix} \qquad
    \begin{bmatrix} 1&3&4\\2&5&6 \end{bmatrix} \qquad
                             \begin{bmatrix} 1&3&5\\2&4&6 \end{bmatrix} 
  \end{align*}
\item the number of permutations $\sigma$ of $1,\dots,2n$ such that
  \begin{enumerate}
  \item $\sigma = \sigma^{-1}$,
  \item $\sigma(a) \ne a$ for all $a$,
  \item If $a<b<c<d$ and $\sigma(a)=c$, then $\sigma(b) \ne d$.
  \end{enumerate}
  When $n=3$, here are the permutations (written in 1-line notation $\sigma(1)\sigma(2)\cdots \sigma(6)$):
  \[
    432165,\quad
    632541,\quad
    216543,\quad
    214365,\quad
    654321.
  \]
\end{enumerate}

\item Consider the following variation of counting balanced parentheses. We have a new symbol $*$. Let $a_n$ be the number of length $n$ strings consisting of left/right parentheses and $*$ such that the result of deleting all of the $*$'s is a balanced set of parentheses ($a_0=1$). Let $A(x) = \sum_{n \ge 0} a_n x^n$. Find a nonzero expression $a(x) t^2 + b(x) t + c(x)$, where $a(x),b(x),c(x)$ are polynomials in $x$, such that plugging in $t=A(x)$ gives $0$.

  \section{Optional problems (don't turn in)}

\item Show that the number of ways of triangulating (i.e., drawing diagonals between vertices that do not intersect except at vertices so that the regions are all triangles) a convex polygon with $(n+2)$ vertices is the Catalan number $C_n$. By convention, the ``2-gon'' and triangle both have exactly one triangulation and here are the 5 triangulations of a pentagon:
  \[
    \begin{tikzpicture}
      \draw (18:1cm) -- (90:1cm) -- (162:1cm) -- (234:1cm) -- (306:1cm) -- cycle;
      \draw (234:1cm) -- (18:1cm) -- (162:1cm);
\foreach \x in {18,90,162,234,306}{
\filldraw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\qquad
    \begin{tikzpicture}
      \draw (18:1cm) -- (90:1cm) -- (162:1cm) -- (234:1cm) -- (306:1cm) -- cycle;
      \draw (18:1cm) -- (162:1cm) -- (306:1cm);      
\foreach \x in {18,90,162,234,306}{
\filldraw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\qquad
    \begin{tikzpicture}
      \draw (18:1cm) -- (90:1cm) -- (162:1cm) -- (234:1cm) -- (306:1cm) -- cycle;
\draw (306:1cm) -- (90:1cm) -- (234:1cm);      
\foreach \x in {18,90,162,234,306}{
\filldraw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\qquad
    \begin{tikzpicture}
      \draw (18:1cm) -- (90:1cm) -- (162:1cm) -- (234:1cm) -- (306:1cm) -- cycle;
      \draw (90:1cm) -- (234:1cm) -- (18:1cm);
\foreach \x in {18,90,162,234,306}{
\filldraw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
\qquad
    \begin{tikzpicture}
      \draw (18:1cm) -- (90:1cm) -- (162:1cm) -- (234:1cm) -- (306:1cm) -- cycle;
      \draw (90:1cm) -- (306:1cm) -- (162:1cm);
\foreach \x in {18,90,162,234,306}{
\filldraw (\x:1cm) circle (2pt);
}
\end{tikzpicture}
  \]
\end{enumerate}
\end{document}
