\magnification=\magstephalf\nopagenumbers
\input amstex
%\voffset=-.8truein
%\hoffset=-.5truein\hsize=7.25 truein\vsize=10.8truein
%\baselineskip=10.35pt
\parskip=5pt\lineskiplimit=-2pt\lineskip=1pt
\centerline{HOMEWORK SET \#7 / Sample midterm / CO1A/ Spring 2020} \vskip3mm
\rightline{as was the MIDTERM / CO1A   /   Fall 2019 \hskip 2cm  }
\vskip4mm

\item{1.)} In how many ways can we choose 8 bottles of soda if
there are 12 brands available, if
\itemitem{a.)} order counts and repetition is allowed?
\itemitem{b.)} order does not count and repetition is allowed?
\itemitem{c.)} order counts and repetition is not  allowed?
\itemitem{d.)} order does not count and repetition is not allowed?
{\bf (8~points)}

\item{2.)} How many $n\times m$ matrices do you have ($n$ rows and $m$ columns) whose entries
are only 0's or 1's and all rows are different? {\bf (5~points)}

\item{3.)}
How many different ways can exactly one gentleman get
his coat back if $n$ of them checked their coat in the cloakroom
and they get them back randomly.
 {\bf (6~points)}



\item{4.)} Find both the recurrence relation and the appropriate
generating function (not from the RR) for the number of $n$-digit numbers (over
$\{0,1,\ldots,9\}$) where digit 0 can be used only even number of
times. Use the generating function to find the number! (Note: the
$n$-digit numbers may begin with an arbitrary number of zeroes)
{\bf (6~points)}


\item{5.)} Determine a recurrence for $f(n)$, the number of the
regions the 3D space is divided by $n$ balls of general position
(i.e. each pair of them intersect in a circle, each three of them
have exactly two common points and no four of them have a common
point). You do not have to solve the recurrence relation! {\bf (6~points)}


\item{6.)} Find the ordinary generating function of the sequence
$n^2$, i.e. find a close formula for the function
$\sum_{n=0}^\infty n^2\cdot x^n$.
{\bf (5~points)}





  \item{7.)}Suppose that there are $2p$ kinds of objects, each in infinite
supply. Let $a_k$ be the number of distinguishable ways of
choosing (without order) $k$ objects if only an even number
(excluding 0) of each of the first $p$ kinds of object  and an odd
number of each of the second $p$ kinds of object  can be taken.
Set up a generating function for the sequence $(a_k)$ and solve
for $a_k$. {\bf (6~points)}




\item{8.)} You must sit $n$ pairs of policemen around a round
table such that no policemen from the same pair are sitting next
to each other. How many different ways can you do that? {\bf (6~points)}



\bye


\item{1.)}  How many $n\times m$ matrices do we have ($n$ rows and $m$ columns) whose entries
are only 0's or 1's and all rows are different?  {\bf (4~points)}



\item{2.)} Determine a recurrence for $f(n)$, the number of regions
into which the space is divided by $n$ planes in general position
(planes are in general position if each two intersect in a line, each three in a single point and no four share a point).
Solve the recurrence to obtain the number of parts. {\bf (7~points)}


\item{3.)} Find the ordinary generating function of the sequence
$n^2$, i.e. find a close formula for the function
$\sum_{n=0}^\infty n^2\cdot x^n$.
{\bf (6~points)}


\item{4.)} 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$.  {\bf (5~points)}


\item{5.)}  Use the recurrence relation derived in class for $D_n$,
the number of derangements of $n$ objects to prove that
$D_{n+1}=(n+1)D_n+(-1)^{n+1}$. Solve this later recurrence relation
(with the known initial values) for $D_n$.  {\bf (7~points)}


\item{6.)} Find the number of permutations of the set
$\{1,2,\dots,n\}$ in which the patterns
 $12, 23, 34, \dots, (n-1)n$\quad do not appear.{\bf (6~points)}


\item{7.)} Compute $S(n,4)$ and $S(n,n-4)$ with any of the methods
covered in class. {\bf (7~points)}


\item{8.)}Remember that the Fibonacci numbers are defined by
$F_{n}=F_{n-1}+F_{n-2}$ and $F_0=F_1=1$. Prove that for every pair
$m\ge 0$,\ \ $n>0$ \ $F_{n+m+1}=F_{n-1}F_m+F_nF_{m+1}$. {\bf
  {\bf (6~points)}



\bye


