% LaTex2e
\documentclass[12pt]{article}
\pagestyle{empty}
\usepackage{amssymb,latexsym}

\newcount\probno
\probno=0
\def\prob{\advance\probno by 1 \bigskip\par\noindent\the\probno . }

\newenvironment{enum}
{\begin{list}{(\alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

\def\comb(#1,#2){
\left(
\begin{array}{c}
#1 \\
#2 
\end{array}
\right)
}
\begin{document}

\centerline{A. Miller \hfill M475 \hfill Final \hfill Spring 2010}

\begin{center}
  Instructions
\end{center}

\underline{Do not hand in this sheet.} Show all work. Write clearly and
carefully.

\bigskip

\def\su{\subseteq}

% chapt 2 - 54
\prob Determine the size of the set
$$\{(A,B,C)\;:\; A\su B\su C\su \{1,2,\ldots,n\}\}$$
and explain why it is correct.

% chapt 3 - 20
\prob (a) Prove that $r(3,3,3)\leq 17$.

This is equivalent to: 

The line segments joining 17
points are arbitrarily colored
red, white, or blue.  Prove that there must exist three points such that
the three line segments joining them are all red, all white, or
all blue.

You may assume without proof that
$r(3,3)\leq 6$.

\par (b) Using an analogous argument, for what $N$ could
it be shown that $r(3,3,3,3)\leq N$?   You do not need to give the argument.

% chapt 6-16
\prob Use combinatorial reasoning to derive the identity:
$$ n!=\comb(n,0)D_n+\comb(n,1)D_{n-1}+\cdots+\comb(n,n-1)D_1+
\comb(n,n)D_0$$
For $k\geq 1$, $D_k$ is the number of derangements of $
\{1,2,\ldots,k\}$ and
$D_0=1$ by convention to make the above formula true.

% chapt 7-9
\prob
Let $h_n$ equal the number of ways in which the squares of a 1-by-n
chessboard can be colored using the colors red, white, and blue
so that no two squares that are colored red are adjacent and
no two squares that are colored white are adjacent.  Find
a recurrence relation that the $h_n$ satisfy.  Explain how you
obtained it and why it is correct.

% chapter 7-18
\prob Determine the generating function for the number $h_n$ of
nonnegative integral solutions of
$$i+2j+3k=n$$
and explain why it is correct.

\newpage
% chapter 8-17
\prob Recall that the  Stirling numbers 
of the second kind, $S(n,k)$, are the number of partitions of
the set $\{1,2,\ldots,n\}$ into $k$ nonempty parts.
\par (a) State a Pascal-like recurrence formula for
the $S(n,k)$ and explain why it is true.
\par (b) Use this formula to compute the triangular table for 
$S(n,k)$ for
\par\noindent $1\leq k\leq n\leq 6$.


% chapter 8-27
\prob 
\par(a) Explain why the number of self-conjugate partitions of $n$ is
the same as the number of partitions of $n$ into distinct odd parts.
\par(b) For each integer $n>2$ determine a self-conjugate partition
of $n$ that has at least $\lceil{n\over 2}\rceil$ parts.

\def\aa{{\mathcal A}}

% chapter 9-8
\prob 
\par (a) Let $\aa=(A_1,\ldots,A_n)$ be a sequence of sets.
Explain what an SDR for $\aa$ is.
\par (b) Suppose that $\aa$ has an SDR
and $x\in A_1$. Prove that $\aa$ has an SDR containing $x$.
\par (c) Show by example that it may not be possible to find
an SDR in which $x$ represents $A_1$.

\def\vs{$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;$}

% chapter 9-19
\prob 
\par (a) Explain what an unstable complete marriage is.
\par (b) Use the deferred acceptance algorithm due to
Gale-Shapley to obtain
a stable complete marriage for the preferential
rankings:

\vs $a_1:\;\;\;\;$ $b_1<b_2<b_3$ \vs  $b_1:\;\;\;\;$ $a_3<a_2<a_1$

\vs $a_2:\;\;\;\;$ $b_1<b_3<b_2$ \vs  $b_2:\;\;\;\;$ $a_1<a_2<a_3$

\vs $a_3:\;\;\;\;$ $b_2<b_1<b_3$ \vs  $b_3:\;\;\;\;$ $a_1<a_3<a_2$

\medskip
\noindent e.g., $a_3$ prefers $b_2$ to $b_1$ and $b_1$ to $b_3$.

\prob
Ten books numbered 1-10 are to be put onto three shelves numbered
1-3. How many ways can this be done, if each shelf must have at
least one book and the ordering of the books on each shelf matters?


For example: 

shelf 1: 2,8,4 $\;\;\;$ 

shelf 2: 9,7,3 $\;\;\;$ 

shelf 3: 1,10,5,6 





\newpage
\begin{center}

Sketch Answers

\end{center}

1. $4^n$

2. (b) 66

3. Partition by the number of fixed points.

4. $h_n=h_{n-1}+4h_{n-2}$

5. $\sum x^i\;\;\sum x^{2j}\;\;\sum x^{3k}$

6. (a) $S(n+1,k)=kS(n,k)+S(n,k)$

7. (b) e.g. for n=7:  7=4+1+1+1

8. (c) $A_1=\{x,y\}\;\; A_2=\{x\}$

9. $(a_1,b_2)\;\; (a_2,b_3)\;\; (a_3,b_1)$

10. $10!\comb(9,2)$
\end{document}




