\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{ps7}{Problem Set 7}{March 29, 1994}

\pset{7}
{\bf Reading:\ } Sections 2.1--2.3, 2.5 of Liu
(handout \ref{Liu}).

\medskip

The problems
%\footnote{The authors are deeply indebted to a number of sources
%which will remain nameless (seeing that some of them contain answers to 
%the problems.)} 
are divided into oral problems (prefix~``{\bf O}'') and
written problems (prefix~``{\bf W}'').
The oral problems are due in tutorial on Monday, April 4.  
{\bf The written problems are due at the beginning of class on Thursday,
April 7.}  Remember to write up each problem on a separate page or
pages, with your name on each sheet.  

\medskip


\medskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Calculate the coefficients of each of the 
following series.

\begin{problemparts}

\problempart
\[ {1\over (1+x)^m} \]
where $m$ is an natural number.

\problempart
\[ \ln(1+3x) \]

\problempart
\[ x^5 \sin(x^2) \]

\problempart
\[ x^2 + {1\over 1-x}\]

\problempart
\[ (x+5)^4 \]


\problempart
\[ {1\over \cos (x)} \]
You only need to calculate the first 4 terms of this series.

\end{problemparts}

\goodbreak

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Compute (ordinary) generating functions for each of the following 
sequences.

\begin{problemparts}

\problempart
\[ (1,1,1,0,0,0,0,0,0,\ldots)  \]

\problempart
\[ (0,0,0,1,1,1,1,1,\ldots ) \]

\problempart
\[ (0,0,0,1,1,2,1,1,1,1,1\ldots )  \]

\problempart
\[ (0,0,0,1,2,4,5,6,7,8,9\ldots )  \]

\problempart
\[ (a_k)=\left(2\over k!\right)  \]

\problempart
\[ (a_k)=\left(2^k\over k!\right)   \]

\problempart
\[  (a_k)=\left(2^k\over (k-3)!\right) \]

\problempart
\[  (1,0,0,1,0,0,1,0,0,1,\ldots) \]

\problempart
\[  (0,2,0,0,2,0,0,2/2!,0,0,2/3!,0,0,2/4!,\ldots \]

\problempart
\[  (0,2,0,2,0,2/2!,0,2/3!,0,2/4!,\ldots) \]

\problempart
\[  (0,2,0,-2/3!,0,2/5!,0,2/7!,0,2/9!,\ldots) \]

\problempart
\[  (1,4,9,16,25,\ldots) \]

\problempart
\[  (2,6,12,20,30,42,56,\ldots) \]

\problempart
\[ (a_k)=\sum_{i=0}^k {1\over i!}  \]

\problempart
\[ (a_k)=2^k+3^k  \]


\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Find partial fraction decompositions for the following
generating functions.

\begin{problemparts}

\problempart
\[ {x\over 4x^2-1} \]

\problempart
\[ {x^7+1\over 4x^2-1} \]

\problempart
\[ {x-1/2\over 4x^2-1} \]

\problempart
\[ {x\over x^2+x+1} \]

\problempart
\[ {(x-1)^2\over x^2+x+1} \]

\problempart
\[ {x-3\over x^3+x^2-x-1} \]

\problempart
\[ {1\over x^4-1} \]

\problempart
\[ {x^3\over x^4-1} \]

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem

Find (exactly) the coefficient of $x^n$ in 
\[ {x^4\over x^4-1} \quad. \]
Find a simple asymptotically tight ($\sim$) formula
for the coefficient of $x^n$.

Repeat the above for the generating function
\[ {x^4+x^2\over (x-1)^4} \quad. \]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Suppose we are buying party balloons which come
in 8 different colors called (imaginatively)
$C_1,\ldots,C_8$. Now, balloons of these colors
are sold only in packets of size 
$2,16,2,12,12,4,4,12$ respectively. What's more,
the store you've gone to is down to its last packet
of each color. I.E. if you want color $C_4$, you can 
only buy 0 or 12 ballons. Find a generating function
for the number of ways to have an assortment of $n$
colored balloons.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
A ``crooked die'' is marked with faces
$1,2,3,4,5,7$. Let $f(k)$ be the number of ways
in which the $k$ distinguishable crooked dice
can thrown so that their total is an even number.
Find a simple formula for the ordinary generating function
\[ \sum_{k\ge0} f(k) x^k \quad.\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Let $g(k)$ be the number of $n$-digit words formed
from letters ``a,b,c,d.e'' such there are in total an even number
of of letters ``a'' and ``b.''
Find a simple formula for the ordinary generating function
\[ \sum_{k\ge0} g(k) x^k \quad.\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Let $h(k)$ be the number of $n$-digit words formed
from letters ``a,b,c'' such that no letter appears exactly
three times
Find a simple formula for the ordinary generating function
\[ \sum_{k\ge0} h(k) x^k \quad.\]



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[t]
\centerline{\psfig{figure=figures/fountain.ps,height=1in}}
\figcaption{A block fountain with base of length 13. }
\label{fig:fountain}
\end{figure}

\oproblem

A \defi{block fountain} is an arrangement of rows of coins (or
any other uniformly sized disks) such that each row is a 
contiguous block. Further, if a coin is in any row besides the bottom,
then it rests on two coins in the row below it. 
See Figure~\ref{fig:fountain}. This problem counts the number of
block fountains with base row of length $k$. Call this number
$f(k)$.

\begin{problemparts}

\problempart
By breaking fountains up by removing their bottom rows, show
that $f(k)$ satisfies
\[ f(k)=1+\sum_{j=1}^k (k-j) f(j)  \]
for $k\ge1$, and $f(0)=1$.

\problempart
Use the above recurrence
to find a closed form for the generating function
\[ F(x) = \sum_{i\ge1} f(i)x^i \quad. \] 

\problempart
Find a partial fractions decomposition of $F(x)$.

\problempart
Find a closed form formula for $f(k)$.
Calculate the first 6 values. Do they 
look familiar?
Derive a simple asymptotically tight ($\sim$) bound on the number
of fountains with base $k$.

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[t]
\centerline{\psfig{figure=figures/path.ps,height=1in}}
\figcaption{A lattice path from $(0,0)$ to $(11,6)$}
\label{fig:path}
\end{figure}

\oproblem

A \defi{lattice path} is a path formed by straight lines
in the plane such that each line starts and ends on a
point in $\naturals\times\naturals$. This problem counts
the number of lattice paths from the origin to another
lattice point subject to the restriction that each line
segment must come from a prescribed set. For example,
Figure~\ref{fig:path} is a lattice path with segments
chosen from the set $\{(0,1),(1,0),(1,1)\}$.

\begin{problemparts}

\problempart
Let $f(m,n)$ be the number of lattice paths from
$(0,0)$ to $(m,n)$ using only steps from
$\{(0,1),(1,0)\}$. Find a formula for
\[ \sum_{m,n\ge0} f(m,n) x^m y^n \quad. \]
Can you find a simple combinatorial interpretation
for $f(m,n)$?

\problempart
Let $f(m,n)$ be the number of lattice paths from
$(0,0)$ to $(m,n)$ using only steps from
$\{(0,1),(1,0),(1,1)\}$. I.E. this is the case from
Figure~\ref{fig:fountain}. Find a formula for
\[ \sum_{m,n\ge0} f(m,n) x^m y^n \quad. \]

\problempart
Let $f(m,n)$ be the number of lattice paths from
$(0,0)$ to $(m,n)$ using only steps from
$\{(0,3),(1,0),(4,5)\}$. Find a formula for
\[ \sum_{m,n\ge0} f(m,n) x^m y^n \quad. \]

\problempart
Do you see a pattern?

\end{problemparts}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\oproblem
Define the backwards difference operator on functions
from the natural numbers to the complex numbers by
\[ \nabla f(n) =\left\{ 
  { f(n) - f(n-1) \hbox{$\qquad$ if $n>0$} \atop
    \qquad f(0) \hbox{$\qquad\qquad$ when $n=0$}}
    \right. \quad.\]

\begin{problemparts}

\problempart
Show if $F(x)$ is the (ordinary) generating function
for $f(n)$, then $(1-x)F(x)$ is the  generating function
for $\nabla f(n)$. 

\problempart
Show that if $F(x)=P(x)/(1-x)^{d+1}$ where $P(x)$ is 
a polynomial of degree less than or equal to $d$, then
$F(x)$ is the generating function for some polynomial
of degree $d$. (It turns out the converse is true as well.)

\problempart
Show that if $f(n)$ is  a polynomial, then $\nabla^k f(n)=0$
for sufficiently large $k$ and $n$.

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\wproblem


\begin{figure}[t]
\centerline{\psfig{figure=figures/disjoint.ps,height=1in}}
\figcaption{A tiling divided into 3 disjoint tilings of rectangles. }
\label{fig:disjoint}
\end{figure}


\begin{figure}[b]
\centerline{\psfig{figure=figures/prime.ps,height=1in}}
\figcaption{The ways to tile a rectangle so that it cannot
be divided into tilings of disjoint rectangles. There are
two special cases, one for length 1 tilings and one for length
2 tilings. There are 4 infinite families of tilings, two for
tilings of even length ($\ge2)$ and o} and  two for tilings of
odd length ($\ge3$).
\label{fig:prime}
\end{figure}



Suppose the generating functions $\sum_{i\ge0} a_i x^i$ and $\sum b_i x^i$
can be written as $p(x)/q(x)$ and $r(x)/s(x)$ respectively for some
polynomials $p,q,r,s$. It is an elementary (but nonetheless fairly
deep) fact that $\sum_{i\ge0} a_i b_i x^i$ can also be written as a 
ratio of polynomials.
Thus we now a priori that if $f_i$ is the $i$th Fibonacci number,
then \[\sum_{i\ge0} f_{i+1}^2 x^i=1+4x+9x^2+\cdots\] can be written
as a ratio of polynomials. This problem develops this generating
function explicitly by examining certain tilings of rectangles.
For the purposes of this problem, tiles cannot be rotated.

\begin{problemparts}

\problempart
Give a combinatorial argument
 that the number of ways to tile a $2\times n$ rectangle
with $1\times2$ and $2\times1$ tiles is $F_{n+1}$. Deduce that
the number of ways to tile a $1\times n$ rectangle by $1\times1$
and $1\times2$ tiles is also $F_{n+1}$. Further conclude that
the number of ways to tile a $2\times n$ rectangle by $1\times1$
and $1\times2$ tile is $F_{n+1}^2$.

\problempart
It is possible to divide some such tilings into disjoint parts
by vertical lines.
(Figure~\ref{fig:disjoint}).


Argue briefly that the only tilings that cannot be divided into disjoint
parts are those pictured in Figure~\ref{fig:prime}.




\problempart
Find a closed form for the generating function $\sum_{i\ge0} f_{i+1}^2$.

\problempart
 From your formula for $\sum_{i\ge0} f_{i+1}^2$, derive a simple
 asymptotically tight ($\sim$) bound on
$f_{i+1}^2$.
Does this agree with the asymptotic formula for $f_{i+1}$?




\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\wproblem
A \defi{partition} of a natural number $n$ into $k$ parts is a
sequence of positive integers, $ n_1\le n_2\le \cdots \le n_k$, such that
$n = \sum_{i=1}^k n_i$. 
A part $m$ is said to occur with \defi{multiplicity} $j$ if
precisely $j$ of the $n_1,n_2,\ldots,n_k$ are equal to $m$.
For example $1,2,4,4,6$ is a partition of $17$ into $5$
parts; $4$ has multiplicity $2$ and
all other parts have multiplicity $1$.

\begin{problemparts}

\problempart
Let $p_1(n,k)$ be the number of partitions of $n$ into $k$ 
distinct parts--that is no part occurs with multiplicity greater than 1.
Prove that 
\[ \sum_{n,k\ge0} p(n,k) x^n y^k = 
       \prod_{r\ge1} (1 + y x^r)\quad.\]


\problempart
Prove that setting $y:=1$ in the generating function for $p_1(n,k)$
gives the (ordinary) generating function for the number, call it $p_1(n)$,
of partitions of $n$ with distinct parts. Namely,
\[ \sum_{n\ge0} p_1(n) x^n  = 
       \prod_{r\ge1} (1 +  x^r)\quad.\]

\problempart
Find the coefficients of $x^i y^j$ in the above
generating function for $i,j=0\ldots 3$.

\problempart
Find an (ordinary) generating function for the number, $p_2(n)$, of partitions of $n$ into odd
parts. Use this to show that the number of such partitions is the same of
the number of partitions of $n$ into distinct parts.

\problempart
Let the expression $p(n)$  denote the number of partitions of $n$.
Write down (and justify) an ordinary generating function for $p(n)$. 

\problempart
Generalize the above formulas. Namely, suppose that $M$ and $R$ are
two sets of positive integers. Let $p_{M,R}(n,k)$ be the number of partitions
of $n$ into $k$ parts such that each part is in $R$ and each part occurs with
a multiplicity $m\in M$. Find a simple expression for
\[ \sum_{n,k\ge0} p_{M,R}(n,k) x^n y^k \quad.\]


\end{problemparts} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\wproblem
This problem asks for a solution (in generating functions) to
the question of how many ways can $n$ distinguishable beads be 
strung together to form a collection of necklaces. In particular,
these are real necklaces, so reversing the order of beads on
a necklace doesn't make a new necklace. In real life this corresponds
to flipping the necklace over. Furthermore, let's say we can't make a necklace
from only one or two beads. Call this number $f_n$.



\begin{problemparts}

\problempart
Give a combinatorial argument for the fact that
there are $(n-1)!/2$ different single necklaces made from $n\ge3$
beads. What happens to this argument if $n\le2$?

\problempart
Show that if $F(x)$ is an exponential generating function for 
the number of single necklaces on $n$ beads, then
$\left(F(x)\right)^k$ is the exponential generating
function for the number of ways to build a collection of $k$
necklaces from a total of $n$ beads.


%\problempart
%Show that the exponential generating function for 
%the number of single necklaces on $n$ beads
%is \[ {1\over2}\left( \log{1\over1-x} -x -{x^2\over2} \right)\quad.\]

\problempart
Find an exponential generating function in the variable $x$
such that the coefficient of $x^n$ is the number
of ways to form $k$ necklaces out of $n$ beads.

\problempart
Again, suppose we want to build exactly $k$ necklaces.
Find an exponential generating function 
counting the number of ways to do this
with $n$ or fewer beads.

%\problempart
%Show that 
%\[\sum_{i\ge0} f_i {x^i\over i!} = {e^{-{1\over 2}x-{1\over 4}x^2}\over
%              \sqrt{1-x}}\quad.\]
%Compute $f_0,f_1,f_2,f_3,f_4,f_5,f_6$ using this formula.
%

\end{problemparts}

\end{problems}


\end{document}



