\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath}
\usepackage{tikz}
\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 \#3\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due October 12, 2017}}
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
\begin{document}
\qonly{Show all your work, and explain why you use the arithmetic
  operations you use in reaching an answer.}

\begin{enumerate}
\item \textbf{(10 points)} \question{Prove \emph{combinatorially} that
    for any non-negative $m$ and $n$,
    \[\sum_{k=m}^n \binom nk\stirling km=\stirling{n+1}{m+1}.\]}

  \answer{}

\item \textbf{(10 points)} \question{Recall that a permutation of the
    sequence of numbers $(1,2,3,\ldots,n)$ which does not have any $i$
    in the $i$th position is called a \emph{derangement}, and that the
    number of derangements of length $n$ is called $D_n$. Prove
    \emph{combinatorially} that for $n\geq 2$,
    \[D_n=(n-1)(D_{n-1}+D_{n-2}).\]
    Hint: consider separately the cases when $1$ is simply swapped
    with a different number $k$, versus when it is moved to a position
    $k$ while the value $k$ goes somewhere else completely.}

  \answer{}

\item \textbf{(10 points)} \question{Use inclusion-exclusion (i.e.,
    not brute force) to determine the number of bitstrings
    (i.e. strings of the characters ``0'' and ``1'') of length 7 which
    do not contain the substring ``1111''.}

\item \textbf{(10 points)} \question{A jar contains 5 identical red
    balls, 6 identical blue balls, and far more identical green balls
    than you would ever want. Let $a_n$ be the number of different
    $n$-element collections you could draw from this jar such that you
    draw at least 2 red balls, and the number of green balls drawn is
    a multiple of 3. For instance, $a_5=5$ because the triple of red,
    green, and blue ball counts could be any of $(2,3,0)$, $(2,0,3)$,
    $(3,2,0)$, $(4,1,0)$, or $(5,0,0)$. Answer the following questions
    about this system.}
  \begin{enumerate}
  \item Write a rational function which represents the ordinary
    generating function $\sum_{n=0}^\infty a_nx^n$.

    \answer{}

  \item Calculate $a_{10}$.

    \answer{}

  \end{enumerate}
  
\end{enumerate}
\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      The worst thing you can do is to completely solve a problem. \hfill ---Dan Kleitman
    \end{minipage}
  }
\end{center}
\end{document}
