\magnification=\magstephalf
%\voffset=-.45truein \advance \vsize 1.65truein \hoffset -.5truein \hsize=7.28truein
%\parindent=0pt
%\advance\baselineskip-1pt
\nopagenumbers
\font\eightrm=cmr7
\parskip=4pt
\centerline{HOMEWORK SET \#3 / CO1A / Spring 2020} \vskip12mm

\item{1.} Find the exponential convolution of two sequences, i.e.,  for two given sequences
$(a_n)_{n=0}^\infty$ and $(b_n)_{n=0}^\infty$ define the sequence $(c_n)_{n=0}^\infty=(a_n)
\star(b_n)$ such that if
$f(x)=\sum_{n=0}^\infty {a_n\over n!} x^n$, $g(x)=\sum_{n=0}^\infty {b_n\over n!} x^n$ and $h(x)=\sum_{n=0}^\infty {c_n\over n!} x^n$
then $h(x)=f(x)\times g(x)$.
\item{2.} Suppose that there are $p$ different kinds of objects, each
in infinite supply. Let $a_k$ be the number of ways to pick $k$ of the objects
if we must pick at least one of each kind. Set up a generating function for
$(a_k)$ and find $a_k$ for all $k$.

\item{3.}  Let $p_n^r$ be the number of partitions of the integer $n$
into exactly $r$ parts where order counts. Set up a generating function for the
sequence $(p_n^r)$ and find $p_n^r$.

\item{4.} A codeword from the alphabet $\{a,b,c,d,e,f\}$ is
legitimate iff $a$ and $c$ appear even and $b$ and $d$ appear odd
number of times (no constrain on $e$ and $f$). Find the number of
legitimate codewords of length $k$.
\item{5.} In each of the following, denote by $a_n$ (with an
appropriate choice of $n$) the answer to the question, set up the
appropriate generating function for the sequences $a_n$, indicate
what coefficient (which value of $n$) you are looking for, and
finally calculate the answer to the question.
\itemitem{a.} In how many different ways can 4n letters be selected from $2n$
A's, $2n$ B's and $2n$ C's without order?
\itemitem{b.} Find the number of solutions to the equation
$x_1+x_2+x_3+x_4=18$ where for each $x_i$  $1\le x_i\le 7$ (the
order of the variables counts).
\itemitem{c.}  How many ways can we place 25
indistinguishable balls into  8 distinguishable cells with no
empty cell?
\itemitem{d.} In how many ways can a total of 80 be obtained if 50
distinguishable dice are rolled?
\item{6.}  What is the coefficient of $x^{100}$ in the product
$(1+x+{x^2\over 2!}+{x^3\over 3!}+{x^4\over 4!}+\cdots)\times
(1+{x^2\over 2!}+{x^4\over 4!}+{x^6\over 6!}+\cdots)\times
(x+{x^3\over 3!}+{x^5\over 5!}+\cdots)$?
\item{7.} A codeword over the alphabet $\{0,1,2,3\}$ consists of
at least one of each of the digits  0,1,2 and 3, and has length
20. How many such codewords are there?
\item{8.} Suppose that $G(x)= {x \over x^2-3x+2}$ is the ordinary
generating function of the sequence $(a_k)$. Find $a_k$.
(Hint: factor $x^2-3x+2$ into linear terms and find $G(x)$ as ${a \over \hbox{\eightrm first linear term}} +
{b \over\hbox{\eightrm second linear term}}$)


 \bye
