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

\def\arrow{\to}

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

\def\part#1#2{\left\{
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right\} }

\def\cycle#1#2{\left[
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right] }


\def\rmand{\mbox{ and }}

\pagestyle{empty}

\begin{document}


\begin{flushleft}
          Fall 93\\
          Math 475 \\
          A.Miller
\end{flushleft}


       Due  Wed Dec 1

       Homework assignment    Chapter 8  p. 286-289

\bigskip

\centerline{       1 2 5 11 12 13 15 17 19}

\vspace{1in}

(A)
Let $\part nm =S(n,m)$ be Stirling numbers of the second kind,
i.e., the number of partitions of an $n$-element set into $m$ nonempty
sets.  These numbers satisfy the Pascal-like identity:
$$ \part{n+1}m=\part n{m-1} + m\part nm \rmand \part n1 =\part nn =1.$$
Define
$$S_n(x)=\sum_{m=n}^{\infty}\part mn x^m.$$
Show that $S_n=x(S_{n-1}+nS_n)$.

\bigskip
(B) Show that
$$S_n(x)={{x^n}\over{(1-x)(1-2x)\cdots(1-nx)}}$$

\bigskip
(C) Show that
$$\part{n+1}m=\sum^{n}_{k=m-1}\comb{n}{k}\part k{m-1}.$$
Hint: When partitioning the
set $\{1,2,\ldots,n,n+1\}$ consider the size of the element
of the partition that contains the integer $n+1$.

\bigskip
(D) Let $\cycle nm=s(n,m)$ be the Stirling numbers of the
first kind, i.e., the number of permutations
of an $n$-element set which have exactly $m$ cycles.
These satisfy the identity:
$$ \cycle{n+1}m=\cycle n{m-1} + n\cycle nm \rmand
\cycle n1=(n-1)!,\; \cycle nn=1.$$
Show that
$$x(x+1)(x+2)\ldots(x+n-1)=\sum_{m=1}^{n}\cycle nm x^m.$$

\bigskip
(E) Find a simple expression for
$$\sum_{1\leq k_1<k_2<k_3<\cdots<k_m\leq n-1}k_1k_2\cdots k_m.$$
Hint: use (D).

\vspace{1in}
\begin{center}
  Extra credit problem
\end{center}

(X) How many paths are there from $(0,0,0)$ to $(n,n,n)$ if
each move is one of the following:
\begin{itemize}
  \item $(x,y,z)\arrow (x+1,y,z)$, or
  \item $(x,y,z)\arrow (x,y+1,z)$, or
  \item $(x,y,z)\arrow (x,y,z+1)$.
\end{itemize}
and at all times $x\leq y\leq z$?


\end{document}