\input lmacros
\documentstyle[12pt]{article}
\headheight 0in
\headsep 0in
\evensidemargin 1in
\oddsidemargin \evensidemargin
\textwidth 6.5in
\topmargin 1.25in
\textheight 8.7in
\begin{document}
\pagestyle{empty}

\begin{center}
{\bf Notes:  Stirling numbers.}
\end{center}

The {\it Stirling numbers of the
second kind} are defined by
$$ S(k,n) = \mbox{{\rm number of partitions of a $k$-element set into $n$
blocks.}} $$

For example, $S(4,2) = 7$ and here are the partitions:
$$ \{123 \}\{4 \},\quad\{124 \}\{3 \},
\quad\{134 \}\{2 \},\quad\{234 \}\{1 \},
\quad\{12 \}\{34 \},\quad\{13 \}\{24 \},
\quad\{14 \}\{23 \}. $$
(In some books you will see the {\it Bell numbers} $B_0,B_1,B_2,...$,
with $B_{k}$ defined to be
the number of all partitions of a $k$-element set.  In other words,
since every partition has from 1 to $k$ blocks, $B_{k} = S(k,1)+\cdots
+S(k,k)$.)

An important property of the numbers $S(k,n)$, which is sometimes used
as their definition, is the identity
$$ x^{k} = \sum _{n} S(k,n)[x]_{n}.\eqno (1) $$
Note that we need not specify the summation limits explicitly since
$S(k,n)$ is zero by definition outside the range $1\leq n\leq k$.

Let us give a combinatorial proof of identity (1).  Since both sides
are polynomials in $x$, it is enough to prove it for $x$ a positive
integer.  In that case, let $X$ be a set with $x$ elements.  The left
side of (1) counts functions from $[k]$ to $X$.  Let's see how many
functions take exactly $n$ distinct values.  To choose such a
function $f$, we can first choose the partition of $[k]$ into $n$ blocks
corresponding to the $n$ values to be taken.  This can be done
$S(k,n)$ ways.  Then we choose the values $f$ takes on each block;
this can be done in 
$x(x-1) \cdots (x-n+1) = [x]_n$ ways.  By multiplication, there are
$S(k,n)[x]_{n}$ functions from $[k]$ to $X$ taking exactly $n$
values, and summing over the possibilities for $n$ gives (1).

In the calculus of finite differences, identity (1) is used when expanding a
polynomial $p(x)$ in terms of the polynomials ${x\choose n }$.  (1)
tells us how to expand each power of $x$ in terms of the polynomials
$[x]_{n}$, and then we need only recall that $[x]_{n} = n!{x\choose n }$.

Example: expand $2x^{3}-x^{2}$ in binomial coefficients ${x\choose n }$.

Solution: by (1) and the table of $S(k,n)$ below, $x^{3} = [x]_{3} +
3[x]_{2} + [x]_{1}$ and $x^{2} = [x]_{2} + [x]_{1}$.  Combining, 
$2x^{3} - x^{2}$
= $2(x)_{3}+ 5(x)_{2} + x$ = $12{x\choose 3 } + 10{x \choose2
}+{x\choose 1 }$.

Using finite differences, we have another way to expand $p(x)$: the
coefficient of ${x\choose n}$ is equal to the first entry in row $n$ of
the difference table.  In the example above, the table would be
$$ \begin{array}{ccccccccccl}
p(0)&&p(1)&&p(2)&&p(3)&&p(4)&&\cdots \\
0 &&  1  && 12  && 45 && 112 &&\cdots \\
&  1 &&  11  && 33 && 67 &&&\cdots \\
&&   10   &&  22 && 34 &&&&\cdots \\
&&&      12 &&  12 &&&&&\cdots \\
&&&& 0 &&&&&&\cdots 
\end{array} $$

We can use the shift-operator formalism
to find an explicit formula for the first entry
in any row of the difference table of the sequence $p(0),p(1),p(2),...\,$.
For by the binomial theorem
\begin{eqnarray*}
\Delta^n p & = & (S - I)^n p \\
& = & \sum_{j=0}^n {n \choose j} S^j \: (-I)^{n-j} p \\
& = & \sum_{j=0}^n (-1)^{n-j} {n \choose j} S^j p,
\end{eqnarray*}
so
\begin{eqnarray*}
(\Delta^n p)(0) & = & \sum_{j=0}^n (-1)^{n-j} {n \choose j} (S^j p)(0) \\
& = & \sum_{j=0}^n (-1)^{n-j} {n \choose j} p(j) . 
\end{eqnarray*}
Taking $p(x)$ to be $x^{k}$ in the preceding equation,
and recalling that $S(k,n)$ is the first entry
in the $n$th row of the difference table for $x^k$,
we get a {\it formula} for $S(k,n)$:
$$ n!S(k,n) = \sum_{j=0}^{n} (-1)^{n-j}{n\choose j }j^{k}. $$
This is a formula we proved in class
as an application of the inclusion-exclusion principle.

Another way to compute $S(k,n)$, which is the most practical for
making tables, is by means of the recurrence
$$ S(k,n) = S(k-1,n-1) + nS(k-1,n) \eqno (2)$$
for $k>0$, starting with $S(0,n) = 1$ if $n = 0$, $0$ if $n\not = 0$.
This can be arrived at in a simple combinatorial way.  We wish to
partition $K = \{1,\ldots,k \}$ into $n$ blocks.  Let's try to do it
by first partitioning $\{1,\ldots,k-1 \}$, then adding the element
$k$.  There are two cases:  $k$ forms a block by itself in the final
partition, in which case $\{1,\ldots,k-1 \}$ is partitioned into $n-1$
blocks, or else $k$ goes in with other elements, in which case
$\{1,\ldots,k-1 \}$ is partitioned into $n$ blocks, and there are $n$
choices for which block to include $k$ in.

Recurrence (2) can also be derived algebraically from identity (1).

\medskip

OK, so what are the Stirling numbers of the {\it first} kind?  They
come from the theory of finite differences and are defined by the
``inverse'' to identity (1), that is, as the coefficients expanding
$[x]_{n}$ in terms of $x^{k}$:
$$ [x]_{n}  = \sum s(n,k) x^{k}.\eqno (3)$$
We use the lower case $s$ instead of $S$ to denote these.

Unlike (1), (3) can be read as a direct rule for computing $s(n,k)$,
since we can multiply out $(x)_{n} = x(x-1)\cdots (x-n+1)$ and just
see what the coefficients are.  For example
$$ (x)_{4} = x(x-1)(x-2)(x-3) = x^{4} - 6x^{3}+11x^{2}-6x $$
so 
$$ s(4,4) = 1,\quad s(4,3) = -6,\quad s(4,2) = 11,\quad s(4,1) = -6. $$
Certain observations can be made directly from this rule for computing
$s(n,k)$.  For instance, $s(n,n) = 1$, $s(n,1) = (-1)^{n-1}(n-1)!$,
and the numbers $s(n,k)$ alternate in sign as $k$ varies.

Since some of the numbers $s(n,k)$ are negative, they can't have a
direct combinatorial interpretation.  However, we can define the {\it
signless Stirling numbers of the first kind} to be $c(n,k) =
(-1)^{n-k}s(n,k)$.  These will be non-negative integers, and they do
have a combinatorial significance which we shall see in the context of
permutations.

The numbers $s(n,k)$ also have a recurrence, derivable from (3), which
is 
$$ s(n,k) = s(n-1, k-1) - (n-1)s(n-1, k) $$
for $n>0$.  For $c(n,k)$ this becomes
$$ c(n,k) = c(n-1, k-1) + (n-1)c(n-1, k). $$

You should make a table of Stirling numbers $S(n,k)$, $s(n,k)$
for $1 \leq k \leq n \leq 6$
using the recurrence relations
(and/or generating function techniques).

% NO; I should include it!
% I should also discuss the "convolution" formula for the
% two kinds of Stirling numbers.

\end{document}
