\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}