\documentclass[11pt]{article}
\def\Z{\mathbb{Z}}
\def\Q{\mathbb{Q}}
\usepackage{latexsym,amsmath,amssymb,epsfig}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{MATH 357 -- Combinatorics}
\centerline{Solutions for Problem Set 6}
\centerline{March 24, 2017}
\vskip 10pt
\noindent
5.3.10. (With modified directions!)
There are $13$ different ways to spend exactly $\$15$ corresponding to the partitions of $15$ listed below:
\begin{eqnarray*}
&15\cdot 1 \ ( 15\ {\rm drinks})\\
&1\cdot 3 + 12\cdot 1\ ( 1\ {\rm side\ and\ } 12\ {\rm drinks,\ etc.})\\
&2\cdot 3 + 9\cdot 1\\
&3\cdot 3 + 6\cdot 1\\
&4\cdot 3 + 3\cdot 1\\
&5\cdot 3\\
&1\cdot 5 + 10\cdot 1\\
&1\cdot 5 + 1\cdot 3 + 7\cdot 1\\
&1\cdot 5 + 2\cdot 3 + 4\cdot 1\\
&1\cdot 5 + 3\cdot 3 + 1\cdot 1\\
&2\cdot 5 + 5\cdot 1\\
&2\cdot 5 + 1\cdot 5 + 2\cdot 1\\
&3\cdot 5
\end{eqnarray*}
In terms of generating functions, we want the coefficient of $x^{15}$ in
$$\frac{1}{1 - x}\cdot \frac{1}{1 - x^3}\cdot \frac{1}{1 - x^5},$$
which is equal to 13, either by direct computation or by using Maple.
\vskip 10pt
\noindent
As stated, the problem asks for the number of ways to spend at most $\$15$, so we
want the sum of the coefficients of the $x^i$ for $i = 0,\ldots,15$.  That number is
equal to 87.  The easiest way to find this is to use Maple.  The first line computes
the generating function, the second line computes the Taylor series and gets rid of the
error term that Maple wants to put in the Taylor series formula, and the third
sets $x = 1$ to add up the coefficients:
\vskip 10pt
\centerline{\tt g:=1/(1 - x)*1/(1 - x\^{}3)*1/(1 - x\^{}5);}
\centerline{\tt gp:=convert(taylor(g,x=0,16),polynom);}
\centerline{\tt subs(x=1,gp);}
\vskip 10pt
\noindent
5.3.13.  The number is the coefficient of $x^{100}$ in the Taylor expansion of
$$\frac{1}{1 - x}\cdot \frac{1}{1 - x^3}\cdot \frac{1}{1 - x^{12}}\cdot \frac{1}{1 - x^{30}},$$
which is 282 (computed by way of Maple).
\vskip 10pt
\noindent
5.3.19, 20, 21.  Number 19 was not assigned, but we discussed it in class. Recall that the
idea was that the generating function for the number of distinct partitions of $n$ is
$$D(x) = \sum_{n=0}^\infty d(n) x^n = (1 + x)(1 + x^2)(1 + x^3) \cdots = \prod_{k=1}^\infty (1 + x^k).$$
(Recall, the idea here is that for each $k$, $k$ either appears in the partition of $n$ or
it does not, so the total number of ways to write $n$ as a sum of distinct integers is
the coefficient of $x^n$ in the expansion of this product.
This is also needed for question 21 below, which demonstrates a famous partition identity
originally found by {\it Leonhard Euler} in 1748.  But first, we also need to do
20.  Let $o(n)$ be the number of ways to write
$n$ as a sum of {\it odd positive integers}.  For instance $o(5) = 3$ since the only partitions
of $n = 5$ where all of the parts are odd are $5, 3 + 1 + 1, 1 + 1 + 1 + 1 + 1$.  The generating
function for the $o(n)$ function is
$$O(x)\sum_{n=0}^\infty o(n) x^n = \frac{1}{1 - x}\cdot \frac{1}{1 - x^3}\cdot \frac{1}{1 - x^5} \cdots
= \prod_{k=0}^\infty \frac{1}{1 - x^{2k + 1}}.$$
21.  Then using 19 and 20 (and Fact 5.3.1 from the text), we want to show that
$$D(x)= \prod_{k=1}^\infty (1 + x^k) = \prod_{\ell=0}^\infty \frac{1}{1 - x^{2\ell + 1}} = O(x)$$
One way to do this is to note that the factor $(1 + x^k)$ in $D(x)$ can be written as
$$1 + x^k = \frac{1 - x^{2k}}{1 - x^k}.$$
Hence the product for $D(x)$ can be rewritten as
$$\frac{(1 - x^2)}{(1 - x)}\cdot \frac{(1 - x^4)}{(1 - x^2)} \cdot \frac{(1 - x^6)}{(1 - x^3)} \cdots $$
Canceling factors between the top and the bottom note that all the $(1 - x^{2k})$ (with even exponents)
appear once in the numerator and once in the denominator.  Hence everything on the top cancels, and the 
terms that are left on the bottom are exactly the $(1 - x^{2\ell + 1})$ (with odd exponents).  But
the product of those factors is exactly $O(x)$ by Problem 5.3.20.  Hence $D(x) = O(x)$, and hence
$d(n) = o(n)$ for all $n$:  {\it The number of distinct partitions of $n$ is the same as the number of
odd partitions of $n$ for all $n$}.  
\vskip 10pt
\noindent
5.4.6.  The way to approach this is to use the general Inclusion-Exclusion relation with
two sets.  As mentioned in the email I sent out before the due date, the 
first equation should be
$$x_1 + 3x_2 + 5x_3 + 7x_4 = 15.$$
 If $A_1$ is the set of solutions of the first equation and $A_2$ is the set
of solutions of the second, for the solutions of the first {\it or} the second,
we want to count $|A_1 \cup A_2|$.  By the basic Inclusion-Exclusion Principle,
$$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|.$$
Now $|A_1|$ is the coefficient of $x^{15}$ in the expansion of
$$\frac{1}{1 - x}\cdot \frac{1}{1 - x^3} \cdot \frac{1}{1 - x^5} \cdot \frac{1}{1 - x^7}$$
which is $|A_1| = 19$.  Similarly $|A_2|$ is the coefficient of $x^{17}$ in the expansion
of
$$\frac{1}{1 - x^3}\cdot\frac{1}{1 - x^4}\cdot \frac{1}{1 - x^6} \cdot \frac{1}{1 - x^2}$$
which is $|A_2| = 13$.  Now we count $|A_1\cap A_2|$ with the coefficient of $u^{15}v^{17}$
in the expansion of
$$\frac{1}{1 - uv^3}\cdot \frac{1}{1 - u^3v^4} \cdot \frac{1}{1 - u^5v^6}\cdot \frac{1}{1 - u^7v^2}$$
which is $1$ (the unique solution is $(x_1,x_2,x_3,x_4) = (3,0,1,1)$).  Therefore the number we want is 
$19 + 13 - 1 = 31$.
\vskip 10pt
\noindent
6.1.14.  Refer to Figure 6.1 on page 149.  Let $V_n$ be the number of points where two or more
lines come together in the Sierpinski graph $S_n$.  Then $V_0=3$, $V_1 = 6$, $V_2 = 15$.  
To derive a recurrence, note that in general if $n \ge 1$, $S_n$ consists of three copies of $S_{n-1}$, glued
together in pairs at the three points that are the corners of the central triangle.  This means that
$V_n = 3V_{n-1} - 3$ since $3V_{n-1}$ counts each of the ``gluing points'' twice.  This is an inhomogeneous
first order recurrence with constant coefficients.  
\vskip 10pt 
\noindent
6.1.15.  Let $S_n = \sum_{i=1}^n i^3$.  Then $S_{n+1} = S_n + (n+1)^3$, and $S_1 = 1$ This is an inhomogeneous first
order recurrence with constant coefficients.  The $(n+1)^3$ is a known function of $n$ that makes the recurrence
inhomogeneous.
\vskip 10pt
\noindent
6.1.18.  The recurrence relation is $d_{n+1} = d_n + (n + 1)$, with initial condition $d_1 = 2$.
This is an inhomogeneous first order recurrence
with constant coefficients.  
The way to see this is to think about the configuration with $n$ lines and $d_n$ regions
in the plane with boundaries made up of parts of those lines.  Note that each line is 
subdivided into $n$ intervals (some finite, some infinite) by the remaining $n - 1$ lines.  
Now add the $(n+1)$st line.  Since no lines are
parallel and no three meet in one point, that new line intersects each of the previous $n$ lines in a single 
point, and that lies in one of the $n$ intervals noted before.  As a result, exactly $n + 1$ of the regions we had
before are subdivided into two new regions by the $(n+1)$st line.  It follows that $d_{n+1} = d_n + n + 1$.  (This says, for instance that $d_2 = 4$, $d_3 = 7$, $d_4 = 11$, and so forth.  
\end{document}
