\documentclass[12pt]{article}

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

\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 \#4\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due October 31, 2017}}
\DeclareRobustCommand{\stirling}{\genfrac\{\}{0pt}{}}
\begin{document}
\begin{enumerate}
\item \textbf{(10 points)} \question{Let $p_n(k)$ represent the number
    of partitions of the integer $k$ into exactly $n$ positive integer
    parts, as seen in class.}

    \begin{enumerate}
    \item \textbf{(7 points)} \question{Prove combinatorially that for any
        positive $k$ and $n$,
        \[p_n(k)=p_{n-1}(k-1)+p_n(k-n)\]
        (Hint: a partition either has a part of size 1 or it does not.)}

      \answer{

      }
      
    \item \textbf{(3 points)} \question{Using the above recurrence,
        together with the fact that $p_0(0)=1$ and $p_n(k)=0$ when
        $k<n$ or $n=0$ and $k>0$, calculate $p_4(10)$.}
      
      \answer{
        
      }
    \end{enumerate}

  
  \item \textbf{(10 points)} \question{Let a partition be said to have
      a \emph{squariness} equal to the side-length of the largest
      square which fits into the upper left corner of the Ferrers
      diagram. For instance, the partition of $24$ into
      $6+5+4+4+3+1+1$, as depicted below, has a ``squariness'' of 4.
      \begin{center}
        \begin{tikzpicture}[scale=0.25]
          \draw[red] (-0.4,0.4) rectangle (3.4,-3.4);
          \foreach \x in {0,...,5} {
            \fill (\x,0) circle (0.3);
          }
          \foreach \x in {0,...,4} {
            \fill (\x,-1) circle (0.3);
          }
          \foreach \x in {0,...,3} {
            \fill (\x,-2) circle (0.3);
          }
          \foreach \x in {0,...,3} {
            \fill (\x,-3) circle (0.3);
          }
          \foreach \x in {0,...,2} {
            \fill (\x,-4) circle (0.3);
          }
          \fill (0,-5) circle (0.3);
          \fill (0,-6) circle (0.3);
        \end{tikzpicture}
      \end{center}
    }
    
    \begin{enumerate}
    \item \textbf{(5 points)} \question{Prove combinatorially that the
        number of partitions of the number $n$ which have squariness
        of $s$ is
        \[\sum_{i=0}^{n-s^2}p_s(i+s)p_s(n-s^2-i+s).\]}

      \answer{
        
      }
      
    \item \textbf{(5 points)} \question{Use the decomposition you
        produced in the previous part to argue that
        \[\prod_{k=0}^\infty\frac1{1-x^k}=\sum_{s=0}^\infty x^{(s^2)}\left(\prod_{i=1}^s\frac1{1-x^i}\right)^2\]
      }
      
      \answer{
        
      }
    \end{enumerate}  
  \item \textbf{(10 points)} \question{Let $a_n$ represent the number
      of strings consisting of the letters A, B, C, and D with at
      least one C, at least two Ds, and with an even number of Bs.}
    \begin{enumerate}
    \item \textbf{(6 points)} \question{Produce a closed formula for the
        exponential generating function
        $\sum_{n=0}^\infty a_n\frac{x^n}{n!}$.}

      \answer{
        
      }
      
    \item \textbf{(4 points)} \question{Use the above generating
        function to calculate $a_{10}$.}

      \answer{
        
      }
  \end{enumerate}
\item \textbf{(10 points)} \question{Let $t_n$ represent the number of
    ways to completely tile a $n\times 2$ rectangle with any number of
    copies of the ``L'' triominoes depicted below (in any orientation)
    and $1\times 1$ squares. A single example of a tiling of a
    $6\times 2$ rectangle is shown:
    
    \begin{center}
      \begin{tikzpicture}[scale=0.3]
        \filldraw[thick,fill=blue!50] (0,0)--(2,0)--(2,1)--(1,1)--(1,2)--(0,2)--cycle;
        \draw (0,1)--(1,1)--(1,0);
        \draw (0,-1) node {``L'' triomino};

        \filldraw[thick,fill=red!50] (10,0) rectangle (11,1);
        \draw (10.5,-1) node {$1\times 1$ square};
 %       \draw (25,0) rectangle (31,2);
        \filldraw[thick,fill=blue!50] (27,0)--(25,0)--(25,1)--(26,1)--(26,2)--(27,2)--cycle;
       \filldraw[thick,fill=red!50] (25,2) rectangle (26,1);
       \filldraw[thick,fill=red!50] (27,2) rectangle (28,1);
       \filldraw[thick,fill=red!50] (27,1) rectangle (28,0);
       \filldraw[thick,fill=blue!50] (28,0)--(30,0)--(30,1)--(29,1)--(29,2)--(28,2)--cycle;
        \filldraw[thick,fill=blue!50] (29,2)--(29,1)--(30,1)--(30,0)--(31,0)--(31,2)--cycle;
        \draw (28,-1) node {Tiling of a $6\times 2$ rectangle};
      \end{tikzpicture}
    \end{center}

    \begin{enumerate}
    \item \textbf{(5 points)} \question{Produce (with explanation) a
        recurrence relation and initial conditions for $t_n$.}

      \answer{

      }

    \item \textbf{(5 points)} \question{Use your recurrence to produce
        a closed formula for $t_n$.}

      \answer{
        
      }
    \end{enumerate}
  }

\end{enumerate}
\vfill
\begin{center}
  \fbox{
    \begin{minipage}{6in}
      A matematikus olyan g\'ep, amely k\'av\'eb\'ol t\'eteleket
      gy\'art.\hfill ---Alfr\'ed R\'enyi
 Kleitman
    \end{minipage}
  }
\end{center}
\end{document}
