\documentclass[12pt]{article}

\usepackage[margin=1in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts}
\usepackage{tikz}
\usetikzlibrary{calc}
\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 \#5\answer{ solutions}}
\rhead{\qonly{Name: \framebox{\phantom{Your name goes here}}}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due November 6, 2015}}

\begin{document}
\begin{enumerate}
\item {\bf (10 points)} \question{Let $a_n$ represent the number of
    ways to distribute $n$ blank balls to three labeled boxes such
    that the first box contains an even number of balls, the second
    contains an odd number of balls, and the third contains at least 2
    balls.}

  \begin{enumerate}
  \item \question{Find a closed form for the generating function
      $f(x)=\sum_{n=0}^\infty a_nx^n$.}

    \answer{The generating function associated with the assignment of
      balls to the first box is $1+x^2+x^4+\cdots=\frac1{1-x^2}$; the
      generating function associated with the second box is
      $x+x^3+x^5+\cdots=\frac x{1-x^2}$, and the generating function
      for the third box is $x^2+x^3+x^4+\cdots=\frac{x^2}{1-x}$; their
      product is thus
      \[f(x)=\frac{x^3}{(1-x^2)^2(1-x)}=\frac{x^3}{(1-x)^3(1+x)^2}\]}

  \item \question{Decompose this generating function into partial
      fractions (a calculator or equation-solving system may help).}
    
    \answer{The partial fraction decomposition involves 5 possible
      terms, matching the prototype
      \[\frac{x^3}{(1-x)^3(1+x)^2}=\frac A{1-x}+\frac B{(1-x)^2}+\frac C{(1-x)^3}+\frac D{1+x}+\frac E{(1+x)^2}\]
      which, when multiplying by the common denominator, yields:
      \[x^3=A(1-x)^2(1+x)^2+B(1-x)(1+x)^2+C(1+x)^2+D(1-x)^3(1+x)+E(1-x)^3\]
      We could solve a system of five equations in five unknowns to
      determine this, but it is slightly less painful to begin by using
      the Heaviside method: plugging in $x=1$ we get $1=4C$, and
      plugging in $x=-1$ we get $-1=8E$, so $C=\frac14$ and $E=\frac{-1}8$.
      Now we have only three unknowns:
      \[x^3=A(1-2x^2+x^4)+B(1+x-x^2-x^3)+\frac{1+2x+x^2}4+D(1-2x+2x^3-x^4)-\frac{1-3x+3x^2-x^3}8\]
      \[-\frac18-\frac78x+\frac18x^2+\frac78x^3=A(1-2x^2+x^4)+B(1+x-x^2-x^3)+D(1-2x+2x^3-x^4)\]
      And considered termwise, we see that
      \[\left\{
        \begin{aligned}
          \dfrac{-1}8&=\phantom{+1}A+\phantom1B+\phantom1D\\
          \dfrac{-7}8&=\phantom{+0A+{}}\phantom1B-2D\\
          \dfrac{1}8&=-2A-\phantom1B\\
          \dfrac{7}8&=\phantom{+0A}-\phantom1B+2D\\
          0&=\phantom{+1}A\phantom{+\phantom0B}-D\\
        \end{aligned}
      \right.
      \]
      From which it is easy to determine that $A=D$ and then, adding the
      first and fourth equations, that $A+3D=\frac34$, so
      $A=\frac3{16}$, $D=\frac3{16}$ and
      $B=2D-\frac78=\frac{-1}2$. Thus:
      \[f(x)=\frac1{16}\left[
        \frac 3{1-x}-\frac 8{(1-x)^2}+\frac 4{(1-x)^3}+\frac 3{1+x}-\frac 2{(1+x)^2}\right].
      \]
    }
    
  \item \question{Using your partial fraction decomposition, determine
    a formula for $a_n$.}
  
  \answer{We shall expand terms in our partial fraction
      decomposition to get a power series representation, whose
      coefficient will be $a_n$:
      \begin{align*}
        f(x)
        &=\frac1{16}\left[\frac 3{1-x}-\frac 8{(1-x)^2}+\frac 4{(1-x)^3}+\frac 3{1+x}-\frac 2{(1+x)^2}\right]\\
        &=\frac1{16}\left[3\sum_{n=0}^\infty\binom n0x^n-8\sum_{n=0}^\infty\binom{n+1}1x^n+4\sum_{n=0}^\infty\binom{n+2}2x^n+3\sum_{n=0}^\infty\binom n0(-x)^n-2\sum_{n=0}^\infty\binom{n+1}1(-x)^n\right]\\
        &=\sum_{n=0}^\infty\frac3{16}x^n-\sum_{n=0}^\infty\frac8{16}(n+1)x^n+\sum_{n=0}^\infty\frac2{16}(n+2)(n+1)x^n+\sum_{n=0}^\infty\frac3{16}(-1)^nx^n-\sum_{n=0}^\infty\frac2{16}(n+1)(-1)^nx^n\\
        &=\sum_{n=0}^\infty\frac{-1-2n+2n^2+(1-2n)(-1)^n}{16}x^n
      \end{align*}
      so $a_n=\frac{-1-2n+2n^2+(1-2n)(-1)^n}{16}$, which, notably, is
      in fact always an integer (since it is in fact counting
      something).  }
  \end{enumerate}

\item {\bf (10 points)} \question{Let $a_n$ be the coefficient on
    $x^n$ in the power-series expansion of
    $f(x)=\frac{(1+x^2+x^4)x^2}{(1-x)^3(1-x^3)(1-x^{10})}$ (or,
    equivalently, you could let $a_n=n!f^{(n)}(0)$, using the
    Maclaurin series). Describe a combinatorial question to which
    $a_n$ is the answer (i.e., ``there are $a_n$ ways to perform the
    following process\ldots'').}

  \answer{This power series would reflect a distribution process which
    logically splits into 6 parts, so we might be talking about
    distributions of $n$ identical objects to six recipients, with
    each recipient's rule dictating one part of the given
    function. So, for instance, the factor $(1+x^2+x^4)$ might
    describe recipient A only being allowed to receive 0, 2, or 4
    objects; the factor $\frac{x^2}{1-x}=x^2+x^3+x^4+\cdots$ might
    describe recipient B being required to receive at least 2 objects;
    the two factors $\frac1{1-x}=1+x+x^2+\cdots$ would describe
    recipeints C and D having no restrictions on what they get; the
    factor $\frac1{1-x^3}=1+x^3+x^6+x^9+\cdots$ would require
    recipient E to receive a multiple of 3 objects, and the factor
    $\frac1{1-x^{10}}=1+x^{10}+x^{20}+\cdots$ would require recipient
    F to receive a multiple of 10 objects.}

\item {\bf (10 points)} \question{Explore the conjugates of the
    partitions of $n$ into distinct parts. What property defines
    these partitions, and what is the generating function for the
    number of partitions with this property?}
  
  \answer{The second question is actually the easier one here; the
    partitions being looked at are clearly equinumerous with the
    partitions of $n$ into distinct parts, which it is easy to build a
    generating function for: $(1+x)(1+x^2)(1+x^3)(1+x^4)\cdots$. If
    you want to define a generating function based on the specific
    property we discover in the question, though, read on!

    As to the first question, we might consider describing the
    property of having distinct parts geometrically in terms of the
    Ferrers diagram as having each row of different length, so that
    row lengths are strictly decreasing. Then, on conjugation, we will
    find that column lengths (from left to right) are strictly
    decreasing. Note that two columns of the same length would
    correspond to a row two units longer than its successor, so in
    order to avoid this each row will have to be no more than one unit
    longer than its successor. In other words, we want row lengths
    (i.e., elements of the partition) to consist of at least one
    instance of consecutive sizes, starting with 1.

    As an illustration, let us consider the distinct partitions of 8:
    $8$, $7+1$, $6+2$, $5+3$, $5+2+1$, and $4+3+1$. These have as
    their conjugates $1+1+1+1+1+1+1+1$, $2+1+1+1+1+1+1$,
    $2+2+1+1+1+1$, $2+2+2+1+1$, $3+2+1+1+1$, and $3+2+2+1$. Note that
    each of these consists either solely of 1s, consists of at least
    one 1 and at least one 2, or consists of at least one 1, 2, and
    3, as the above argument suggests should be the case.

    If we want a generating function based on this, then we could sum
    over a range of values for $k$, the size of the largest part, and
    then multiply together selection procedures for the number of
    parts of each size up to $k$, ensuring that each part appears at
    least once:
    \begin{align*}
      \sum_{k=0}^\infty(x&+x^2+x^3+\cdots)(x^2+x^4+x^6+\cdots)(x^3+x^6+x^9+\cdots)\cdots(x^k+x^{2k}+x^{3k}+\cdots)\\
      &=\sum_{k=0}^\infty\prod_{i=1}^k\frac{x^i}{1-x^i}=\sum_{k=0}^\infty\frac{x^{k(k+1)/2}}{\prod_{i=1}^k(1-x^i)}
    \end{align*}
    That this function is identical to the generating function for
    distinct partitions, $\prod_{i=1}^\infty(1+x^i)$, and to the
    generating function for odd partitions,
    $\prod_{i=1}^\infty\frac1{1-x^{2i-1}}$, is not actually that easy
    to show algebraically.}

\item {\bf (10 points)} \question{Let $a_n$ be the number of
    $n$-letter strings consisting of the letters A, B, C, and D with
    at least one A and an even number of Cs.}
  \begin{enumerate}
  \item \question{Find a formula for the exponential generating
      function $\sum_{n=0}^\infty \frac{a_n}{n!}x^n$.}

    \answer{The generating functions associated with the inclusion of
      $A$s is $x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=e^x-1$; both $B$
      and $D$ are associated with the generating function
      $1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=e^x$, while C has
      generating function
      $1+\frac{x^2}{2!}+\frac{x^4}{4!}+\cdots=\cosh(x)=\frac{e^x+e^{-x}}2$. Thus
      this expression as a whole has generating function
      \[f(x)=(e^x-1)(e^x)^2\frac{e^x+e^{-x}}2=\frac{e^{4x}-e^{3x}+e^{2x}-e^x}2\]}
    
  \item \question{Using the above generating function, find a closed
      formula for $a_n$.}

    \answer{Note that, using the known power series for $e^u$:
      \[f(x)=\sum_{n=0}^\infty\frac{\frac{(4x)^n}{n!}-\frac{(3x)^n}{n!}+\frac{(2x)^n}{n!}-\frac{x^n}{n!}}2=\sum_{n=0}^\infty\frac{4^n-3^n+2^n-1}2\frac{x^n}{n!}\]
      so $a_n=\frac{4^n-3^n+2^n-1}2$.}
  \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.\answer{ [A mathematician is a device for converting
        coffee into theorems.]}  \hfill ---Alfr\'ed R\'enyi
    \end{minipage}
  }
\end{center}

\end{document}
