\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,epsfig,anysize}


\pagestyle{empty}

%\input macros
\def\cross{\times}
\def\fillin{\par\noindent
answer:$\underline{\phantom{AAAAAAAAAAAAAAAA}}$
\par\noindent}
\def\rvec#1{\stackrel{\rightarrow}{#1}}
\def\lvec#1{\stackrel{\leftarrow}{#1}}

\newcounter{xprobno}
\newcommand{\xprob}[1]{\addtocounter{xprobno}{1}
   \par\medskip\noindent\thexprobno . \marginpar{(#1 points)} }

\begin{document}

\begin{flushright}
  A. Miller\\
  M475 Exam 2 \\
  Nov 11, 1993
\end{flushright}

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%% chapter 5
\def\comb#1#2{\left(
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right) }

\xprob{15} Prove that for any integer $n>1$:
$$\comb{n}{1}-2\comb{n}{2}+3\comb{n}{3}+\cdots+
   (-1)^{n-1}n\comb{n}{n}=0.$$

\xprob{10} Construct a partition of all subsets of $\{1,2,3\}$ into
symmetric chains.

\xprob{10} What is the coefficient of $x^2y^3z^4$ in
$(6x+5y+4z)^9$?

%%%%%%%%%%%%%%%%%%%%%%%%%% chapter 6


\xprob{15} In how many ways can 6 nonattacking rooks be placed on
the $6 \cross 6$ chess board below with forbidden positions shown by $X$?

$$\begin{tabular}{|c|c|c|c|c|c|}
\hline
       X      &   &   & \phantom{X}  & \phantom{X} &   \\
\hline
       X      &   &   &              &             & X \\
\hline
              &   &   &              &             &   \\
\hline
              & X & X &              &             &   \\
\hline
              & X & X &              &             &   \\
\hline
              &   &   &              &             &   \\
\hline
\end{tabular}
$$

\xprob{15} Given four pairs of gloves, in how many ways can they be
distributed to four persons so that each person receives a left glove and
a right glove from a different pair, i.e., a nonmatching pair.

%%%%%%%%%%%% chapter 7

\xprob{15} Let $h_n$ denote the number of ``comparisons'' required
to sort a list of $2^n$ numbers using the ``merge sort'' technique.
Note that $h_0=0$.  A merge sort is performed recursively
by partitioning the list of $2^{n+1}$ into two sublists of $2^{n}$
each, sorting each of these sublists, and then merging the two lists.
Assume that it takes $2^{n+1}$ comparisons to merge the two sorted
sublists into a single list.  Write a recurrence relation for
$h_{n+1}$ and solve it.

\xprob{10} Let $h_{n+1}=3h_n-2h_{n-1}$ and $h_0=4$ and $h_1=5$.
Find a formula for $h_n$.

\xprob{10} Let $h_n$ be the number of solutions in nonnegative integers
of the equation $a+b+c=n$ where $a$ is even, $b$ is odd,
and $c$ is less than three.
Find the generating function of this sequence and
express it as a rational function, i.e., the quotient of polynomials.

\end{document}