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

%\addtolength{\topmargin}{-.5in}
%\setlength{\textheight}{9in}
%\addtolength{\oddsidemargin}{-.25in}
%\addtolength{\evensidemargin}{-.25in}
%\addtolength{\textwidth}{.5in}

\begin{document}

\pset{8}{November 8, 1994}{In tutorial, November 14 and 15}

{\bf Reading:\ } [Liu], pp. 24--33, 68--73 (Handout~\ref{liu}); 
[MR], Section 9.6.

\bigskip

\begin{problems}

\problem Compute the (ordinary) generating function for each of the
following sequences.

%\begin{multicols}{2}
\bparts
\ppart
$\displaystyle \ang{1,1,1,0,0,0,0,0,0,\ldots}$
\ppart
$\displaystyle \ang{0,0,0,1,1,1,1,1,\ldots }$
\ppart
$\displaystyle \ang{0,0,0,1,1,2,1,1,1,1,1\ldots }$
\ppart
$\displaystyle \ang{0,0,0,1,2,3,4,5,6,7,8,9\ldots }$
\ppart
$\displaystyle \ang{1,0,0,1,0,0,1,0,0,1,\ldots}$
\ppart
$\displaystyle \ang{1,4,9,16,25,\ldots}$
\ppart
$\displaystyle \ang{2,6,12,20,30,42,56,\ldots}$
\ppart
$\displaystyle \ang{a_k} = \ang{k(k+2)}$
\ppart
$\displaystyle \ang{a_k}=\ang{2^k+3^k}$
\ppart
$\displaystyle \ang{a_k}=\ang{1/k!}$
\ppart
$\displaystyle \ang{a_k}=\ang{\sum_{i=0}^k {1\over i!}}$
\ppart
$\displaystyle \ang{1,1/2,1/3,1/4,\ldots}$
\eparts
%\end{multicols}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find partial fraction decompositions for the following functions.

%\begin{multicols}{3}
\bparts

\ppart
$\displaystyle \frac{8x}{ 4x^2 -1}$

\ppart
$\displaystyle \frac{x^4 - x^3 - 6x^2 + 6x + 7}{x^2 + 3x + 2}$

\ppart
$\displaystyle \frac{x-5}{x^3 + x^2 - x - 1}$

\eparts
%\end{multicols}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Use generating functions to solve the recurrence
\[
a_n = \cases{2^n & \mbox{if } n<3 \\
2a_{n-2}+a_{n-3} & \mbox{if } n\geq 3}
\]
Use induction to check your answer.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem A communication channel protocol uses sequences of length $n$
to encode packets, where each sequence is composed of letters in the
set $\set{a,b,c}$ with the restriction that no two $a$'s can occur
consecutively.  Use generating functions to determine how many of the
$3^n$ possible $n$-digit sequences are legal packets.  Also, give a simple
and tight ($\sim$) asymptotic bound for your answer.  (\hint Set up
recurrences for the number of $n$-digit sequences that end with $a$
and for the number that end with $b$ or~$c$.)  

% Use them to find first
% the number of $n$-digit sequences that end with a $b$ or a~$c$.)

\remove{
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \problem Determine the generating function for the number of different
  bags of fruit consisting of apples, oranges, bananas, and pears, such
  that there are an even number of apples, there are at most 2 oranges,
  the number of bananas is a multiple of 3, and there is at most one
  pear.  Then, find a formula for the number of different bags of fruit.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 	% Stolen from Brualdi, p. 246
Let $S$ be the multiset $\set{\infty\cdot a_1,\infty\cdot
a_2, \infty\cdot a_3,\infty\cdot a_4}$.  For each of the following
problem parts, determine the generating function for the sequence
$\ang{g_0,g_1,\ldots}$, where $g_r$ is the number of $r$-combinations
of $S$ with the specified added restriction.
\bparts
\ppart Each $a_k$ occurs an odd number of times.
\ppart Each $a_k$ occurs a multiple of 3 times.
\ppart The element $a_1$ does not occur, and $a_2$ occurs at most once.
\ppart The element $a_1$ occurs 1, 3, or 11 times, and the element $a_2$
occurs 2, 4, or 5 times.
\ppart Each $a_k$ occurs at least 10 times.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Let $G(x) = \sum_n g_n x^n$.
It is easy to see that $g_0 = G(0)$ and $g_1 = G'(0)$,
where $G'(x)$ is the first  derivative of $G$ with respect to~$x$.  
%	g_0 + g_1x + g_2x^2 + \ldots$.  
%	Show that $G(0)=g_0$, and that $G'(0)=g_1$, where $G'(x)$ is the first 
%	derivative of $G$ with respect to~$x$.  
%	What are $G''(0)$ and $G'''(0)$?  
Express $g_n$ in terms of $G^{(n)}(0)$, where $G^{(n)}(x)$ is the $n$th 
derivative of $G$ with respect to~$x$.  \\
Use your answer to provide another proof that 
$$
(1-x)^{-r}=\sum_n {r+n-1\choose n} x^n\ .
$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
In Problem Set 7, we studied the number of ways $p(n,k)$ to partition an 
integer $n\in\nats$ into exactly $k$ positive integers
$a_1\geq \cdots \geq a_k$, such that $a_1+\cdots +a_k=n$.
So for example, $p(7,3) = 4$:
the partitions are 5,1,1; 4,2,1; 3,3,1; and 3,2,2.
Let's define $p(0,0)=1$ and $p(n,0)=0$ for $n>0$.
Of course, $p(n,k)=0$ for $k>n$.

\begin{problemparts}

\problempart
Let $p_1(n,k)$ be the number of partitions of $n$ into $k$ positive integers 
such that no two integers are equal:  $a_1>\cdots > a_k$.
So for example, $p_1(7,3) = 1$:  the only possible partition is $4,2,1$.
Show that the generating function for $p_1(n,k)$ is
\[ 
\sum_{n,k} p_1(n,k) x^n y^k = \prod_{r=1}^\infty (1 + y x^r).
\]

Let $p_1(n)$ be the total number of partitions of $n$ into unequal positive 
integers; that is, $p_1(n) = \sum_k p_1(n,k)$.
What is the generating function for~$p_1(n)$?

%	\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
By generalizing the generating function for $p_1(n,k)$,
show that the generating function for $p(n,k)$ is 
\[
P(x,y)= \sum_{n,k} p(n,k)x^n y^k = \prod_{r=1}^\infty \frac{1}{1-yx^r}.
\]

We know from Problem Set 7 that $p(n,k)=p(n-1,k-1)+p(n-k,k)$.
Show that this recurrence implies $P(x,y) = xy P(x,y) + P(x,xy)$.\\
Verify that $P(x,y)= \prod_{r=1}^\infty (1-yx^r)^{-1}$ satisfies
this equation.  

\ppart 
Let $p_{\rm odd}(n)$ be the number of ways to partition $n$ into
positive odd integers.  So for example $p_{\rm odd}(6)=4$:  the partitions
are $5,1$; $3,3$; $3,1,1,1$;  and $1,1,1,1,1,1$.
Verify that the generating function for $p_{\rm odd}(n)$ is
$$\sum_n p_{\rm odd}(n)x^n = \prod_{r \,\rm odd} \frac{1}{1-x^r}.$$

By equating their generating functions, 
prove the remarkable fact that $p_1(n) = p_{\rm odd}(n)$: 
the number of ways to partition $n$ into odd integers is the same as
the number of ways to partition $n$ into unequal integers. 
For example, we may verify that $p_1(6) = 4$:  the partitions are
$6$; $5,1$; $4,2$; and $3,2,1$. \\
(\hint Use $1-x^2 = (1+x)(1-x)$.)

Can you find a bijection between the set of partitions of $n$ into odd integers
and the set of partitions of $n$ into unequal integers?

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



\remove{
  %%	DONE BY CHARLES IN LECTURE.
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  \problem
  We say a string of parentheses is well-formed if the parentheses ``match up''
  correctly---there are an equal number of right parentheses and left 
  parentheses and no prefix of the string has more rights than lefts.
  Formally, we may give an inductive definition:
  a string $x$ over the alphabet $\set{ \, (,)\,}$ is well-formed if $x$ is 
  either $(\,)$, $(\,w\,)$, or $w\,v$, where $w$ and $v$ are well-formed.

  In this problem, you will count the number $C_n$ of well-formed strings
  of parentheses containing $n$ left-parentheses and $n$ right-parentheses.
  For example, $C_3=5$:  the five strings are
  $((()))$, $()()()$, $(())()$, $()(())$, and $(()())$.
  The numbers $C_n$ are called the \defi{Catalan numbers}.

  \bparts

  \ppart
  Show that the Catalan numbers satisfy the following recurrence:
  \[  C_n = \sum_{k=1}^{n} C_{k-1}\cdot C_{n-k}.  \]
  where $n\geq 1$ and $C_0=1$.

  \ppart
  Use the recurrence above to show that the generating function
  for the Catalan numbers is
  \[ C(x) =\sum_n C_n x^n = \frac{1\pm\sqrt{1-4x}}{2x}.\]

  \ppart 
  Use the generalized binomial theorem to find the 
  coefficient of $x^n$ in the expansion of $(1-4x)^{1/2}$.

  \ppart
  Deduce from your answer to part {\bf (c)}
  that because $C_0=1$, we need the negative square root in $C(x)$.
  Now use $C(x)$ to find that $C_n = \frac{1}{n+1}{2n\choose n}$.

  \eparts
}

\end{problems}

\end{document}
