chap6.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

\qquad\hbox{integer $n>0$}.
\eqno\eqref|stirl1-rec|
\enddisplay
This is the addition-formula analog that generates Table |stirl1-triangle|.

Comparison of \thiseq\ and \eq(|stirl2-rec|) shows that the first term
on the right side is multiplied by its upper index $(n-1)$ in the
case of Stirling cycle numbers, but by its lower index~$k$
in the case of Stirling subset numbers. We can therefore
perform ``"absorption"'' in terms like $n{n\brack k}$ and $k{n\brace k}$,
when we do proofs by mathematical induction.

Every permutation is equivalent to a set of cycles. For example, consider the
permutation that takes $123456789$ into $384729156$. We can conveniently
represent it in two rows,
\begindisplay
&1\,2\,3\,4\,5\,6\,7\,8\,9\cr
&3\,8\,4\,7\,2\,9\,1\,5\,6\,,\cr
\enddisplay
showing that $1$ becomes $3$ and $2$ becomes $8$, etc. The cycle structure
comes about because $1$ becomes $3$, which becomes~$4$, which becomes~$7$,
which becomes the original element~$1$; that's
the cycle $[1,3,4,7]$. Another cycle in this permutation is $[2,8,5]$;
still another is $[6,9]$. Therefore the permutation $384729156$ is
equivalent to the cycle arrangement
\begindisplay
[1,3,4,7]\,[2,8,5]\,[6,9]\,.
\enddisplay
If we have any permutation $\pi_1\pi_2\ldots\pi_n$ of $\{1,2,\ldots,n\}$,
every element is in a unique cycle. For if we start with $m_0=m$ and
look at $m_1=\pi_{m_0}$, $m_2=\pi_{m_1}$, etc., we must eventually
come back to $m_k=m_0$. (The numbers must repeat sooner or later,
and the first number to reappear must be $m_0$ because we know the
unique predecessors of the other numbers $m_1$, $m_2$, \dots,~$m_{k-1}$.)
Therefore every permutation defines a cycle arrangement. Conversely, every
cycle arrangement obviously defines a permutation if we reverse the
construction, and this one-to-one
correspondence shows that permutations and cycle arrangements are
essentially the same thing.

Therefore $n\brack k$ is the number of permutations of $n$ objects
that contain exactly $k$ cycles. If we sum $n\brack k$ over all~$k$, we
must get the total number of permutations:
\begindisplay
\sum_{k=0}^n{n\brack k}=n!\,,\qquad\hbox{integer $n\ge0$}.
\eqno\eqref|sum-to-factorial|
\enddisplay
For example, $6+11+6+1=24=4!$.

Stirling numbers are useful because the recurrence relations \eq(|stirl2-rec|)
and \eq(|stirl1-rec|) arise in a variety of problems. For example, if we
want to represent ordinary powers $x^n$ by falling powers $x\_n$, we
find that the first few cases are
\begindisplay
x^0&=x\_0\,;\cr
x^1&=x\_1\,;\cr
x^2&=x\_2+x\_1\,;\cr
x^3&=x\_3+3x\_2+x\_1\,;\cr
x^4&=x\_4+6x\_3+7x\_2+x\_1\,.\cr
\enddisplay
These coefficients look suspiciously
like the numbers in Table |stirl2-triangle|,
reflected between left and right; therefore we can be pretty confident
that the general formula is\g\vskip20pt We'd better define\smallskip
${n\brace k}={n\brack k}=0$\smallskip
when $k<0@$ and $n\ge0$.\g
\begindisplay
x^n=\sum_k{n\brace k}x\_k\,,\qquad\hbox{integer $n\ge0$.}
\eqno\eqref|expand-ord-to-falling|
\enddisplay
And sure enough,
a simple proof by induction clinches the argument: We have $x\cdt x\_k=
x\_{k+1}+kx\_k$, because $x\_{k+1}=x\_k@(x-k)$; hence $x\cdt x^{n-1}$ is
\begindisplay \openup3pt
x\sum_k{n-1\brace k}x\_k&=\sum_k{n-1\brace k}x\_{k+1}+\sum_k{n-1\brace k}kx\_k\cr
&=\sum_k{n-1\brace k-1}x\_k+\sum_k{n-1\brace k}kx\_k\cr
&=\sum_k\biggl(k{n-1\brace k}+{n-1\brace k-1}\biggr)x\_k
 =\sum_k{n\brace k}x\_k\,.\cr
\enddisplay
In other words, Stirling subset numbers are the coefficients of
"factorial powers" that yield ordinary powers.

We can go the other way too,
because Stirling cycle numbers are the coefficients of ordinary
powers that yield factorial powers:
\begindisplay
x\_^0&=x^0\,;\cr
x\_^1&=x^1\,;\cr
x\_^2&=x^2+x^1\,;\cr
x\_^3&=x^3+3x^2+2x^1\,;\cr
x\_^4&=x^4+6x^3+11x^2+6x^1\,.\cr
\enddisplay
We have $(x+n-1)\cdt x^k=x^{k+1}+(n-1)x^k$, so a proof like the one just
given shows that
\begindisplay
(x+n-1)x\_^{n-1}=(x+n-1)\sum_k{n-1\brack k}x^k=\sum_k{n\brack k}x^k\,.
\enddisplay
This leads to a proof by induction of the general formula
\begindisplay
x\_^n=\sum_k{n\brack k}x^k\,,\qquad\hbox{integer $n\ge0$.}
\eqno\eqref|expand-rising-to-ord|
\enddisplay
(Setting $x=1$ gives \eq(|sum-to-factorial|) again.)

But wait, you say. This equation involves rising factorial powers $x\_^n$,
while \eq(|expand-ord-to-falling|) involves falling factorials $x\_n$.
What if we want to express $x\_n$ in terms of ordinary powers, or if we
want to express $x^n$
in terms of rising powers? Easy; we just throw in some minus signs and get
\begindisplay \openup4pt
x^n&=\sum_k{n\brace k}(-1)^{n-k}x\_^k\,,\qquad\hbox{integer $n\ge0$};
\eqno\eqref|expand-ord-to-rising|\cr
x\_n&=\sum_k{@n@\brack k}(-1)^{n-k}x^k\,,\qquad\hbox{integer $n\ge0$}.
\eqno\eqref|expand-falling-to-ord|\cr
\enddisplay
This works because, for example, the formula
\begindisplay
x\_4=x(x-1)(x-2)(x-3)=x^4-6x^3+11x^2-6x
\enddisplay
is just like the formula
\begindisplay
x\_^4=x(x+1)(x+2)(x+3)=x^4+6x^3+11x^2+6x
\enddisplay
but with alternating signs. The general identity
\begindisplay \postdisplaypenalty=10000
x\_n=(-1)^n(-x)\_^n
\eqno
\enddisplay
of exercise 2.|rising-and-falling|
converts \eq(|expand-ord-to-falling|) to \eq(|expand-ord-to-rising|) and
\eq(|expand-rising-to-ord|) to \eq(|expand-falling-to-ord|) if we negate~$x$.

\pageinsert % have to place this carefully so that \eqnos don't get out of order!
\table Basic "Stirling number identities", for integer $n\ge0$.\tabref|stirling-id1|
\begindisplay\abovedisplayskip=-2pt \belowdisplayskip=5pt \openup4pt%
 \advance\baselineskip0pt plus .5pt  \advance\lineskip0pt plus .5pt
\noalign{\hbox{Recurrences:}}
{n\brace k}&=k{n-1\brace k}+{n-1\brace k-1}\,.\cr
{@n@\brack k}&=(n-1){n-1\brack k}+{n-1\brack k-1}\,.\cr
\noalign{\smallskip\hbox{Special values:}}
{n\brace 0}&={@n@\brack 0}=\[n=0]\,.\cr
{n\brace 1}&=\[n>0]\,;\quad}\hfill{
{@n@\brack 1}&=(n-1)!\,\[n>0]\,.\cr
{n\brace 2}&=(2^{n-1}-1)\[n>0]\,;\qquad}\hfill{
{@n@\brack 2}&=(n-1)!\,H_{n-1}\,\[n>0]\,.\cr
{n\brace n-1}&={n\brack@n-1@}={n\choose 2}\,.\cr
{n\brace n}&={@n@\brack n}={n\choose n}=1\,.\cr
{n\brace k}&={@n@\brack k}={n\choose k}=0\,,\qquad\hbox{if $k>n$}.}\hidewidth{\cr
\noalign{\smallskip\hbox{Converting between powers:}}
x^n&=\sum_k{n\brace k}x\_k=\sum_k{n\brace k}(-1)^{n-k}x\_^k\,.}\hidewidth{\cr
x\_n&=\sum_k{@n@\brack k}(-1)^{n-k}x^k\,;\cr
x\_^n&=\sum_k{@n@\brack k}x^k\,.\cr
\noalign{\smallskip\hbox{Inversion formulas:}}
\sum_k{@n@\brack k}{k\brace m}(-1)^{n-k}=\[m=n]\,;}\hidewidth{\cr
\sum_k{n\brace k}{k\brack m}(-1)^{n-k}=\[m=n]\,.}\hidewidth{\cr
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\endinsert
\pageinsert
\table Additional Stirling number identities, for integers $l,m,n\ge0$.\tabref|stirling-id2|
\begindisplay\abovedisplayskip=-1pt \belowdisplayskip=5pt \openup3pt%
 \advance\displayindent-\parindent\advance\displaywidth\parindent%
 \advance\baselineskip0pt plus .5pt  \advance\lineskip0pt plus .5pt
{n+1\brace m+1}&=\sum_k{n\choose k}{k\brace m}\,.\eqno\eqref|sid-2|\cr
{n+1\brack m+1}&=\sum_k{@n@\brack k}{k\choose m}\,.\eqno\eqref|sid-1|\cr
{n\brace m}&=\sum_k{n\choose k}{k+1\brace m+1}(-1)^{n-k}\,.\eqno\eqref|sid-4|\cr
\noalign{\kern\prevdepth\g\vskip10pt
$n^m(-1)^{n-m}{n\brack m}$\par
\vskip6pt
$\quad=\sum\limits_k\!{\,n\,\brack\, k\,}{-m\choose k-m}n^k\,.$\kern-12pt
\null\g}
{n\brack@m@}&=\sum_k{n+1\brack k+1}{k\choose m}(-1)^{m-k}\,.\eqno\eqref|sid-3|\cr
m!\,{n\brace m}&=\sum_k{m\choose k}k^n(-1)^{m-k}\,.\eqno\eqref|sid-5|\cr
{n+1\brace m+1}&=\sum_{k=0}^n{k\brace m}(m+1)^{n-k}\,.\eqno\eqref|sid-7|\cr
{n+1\brack m+1}&=\sum_{k=0}^n{k\brack m}n\_{n-k}=n!\sum_{k=0}^n{k\brack m}\big/k!\,.\eqno\eqref|sid-6|\cr
{m+n+1\brace m}&=\sum_{k=0}^m\,k\,{n+k\brace k}\,.\eqno\eqref|sid-9|\cr
{m+n+1\brack m}&=\sum_{k=0}^m\,(n+k){n+k\brack k}\,.\eqno\eqref|sid-8|\cr
{n\choose m}&=\sum_k{n+1\brace k+1}{k\brack m}(-1)^{m-k}\,.\eqno\eqref|sid-10|\cr
\noalign{\kern\prevdepth\g\vskip17pt Also,\par\vskip6pt
${n\choose m}(n-1)\_{n-m}$\par\vskip6pt
$\quad=\sum_k{\,n\,\brack\,k\,}{k\brace m}\,,$\par\vskip6pt
a generalization of~\eq(|sum-to-factorial|).\g}
n\_{n-m}\,\[n\ge m]&=
\sum_k{n+1\brack k+1}{k\brace m}(-1)^{m-k}\,.\eqno\eqref|sid-11|\cr
{n\brace n-m}&=\sum_k{m-n\choose m+k}{m+n\choose n+k}{m+k\brack k}\,.\eqno\eqref|sid-13|\cr
{n\brack@n-m@}&=\sum_k{m-n\choose m+k}{m+n\choose n+k}{m+k\brace k}\,.\eqno\eqref|sid-12|\cr
\indent{n\brace l+m}{l+m\choose l}&=\sum_k{k\brace l}{n-k\brace m}{n\choose k}\,.\eqno\eqref|sid-15|\cr
{n\brack@l+m@}{l+m\choose l}&=\sum_k{k\brack l}{n-k\brack m}{n\choose k}\,.\eqno\eqref|sid-14|\cr
\enddisplay
\hrule width\hsize height.5pt
\kern4pt
\endinsert

We can remember when to stick the $(-1)^{n-k}$ factor into a formula
like \eq(|expand-ord-to-rising|) because there's a
natural ordering of powers when $x$ is large:
\begindisplay
x\_^n>x^n>x\_n\,,\qquad\hbox{for all $x>n>1$}.\eqno
\enddisplay
The Stirling numbers $n\brack k$ and $n\brace k$ are nonnegative, so we have
to use minus signs when expanding a ``small'' power in terms of ``large'' ones.

We can plug \eq(|expand-rising-to-ord|) into \eq(|expand-ord-to-rising|) and
get a double sum:
\begindisplay
x^n=\sum_k{n\brace k}(-1)^{n-k}x\_^k
 =\sum_{k,m}{n\brace k}{k\brack m}(-1)^{n-k}x^m\,.
\enddisplay
This holds for all $x$, so the coefficients of $x^0$, $x^1$, \dots,~$x^{n-1}$,
$x^{n+1}$, $x^{n+2}$,~\dots\
on the right must all be zero and we must have the identity
\begindisplay
\sum_k{n\brace k}{k\brack m}(-1)^{n-k}=\[m=n]\,,
\qquad\hbox{integers $m,n\ge0$}.
\eqno\eqref|stirl-inv|
\enddisplay

Stirling numbers, like binomial coefficients, satisfy many surprising
identities. But these identities aren't as versatile as the ones we had
in Chapter~5, so they aren't applied nearly as often. Therefore it's
best for us just to list the simplest ones, for future reference when
a tough Stirling nut needs to be cracked. Tables |stirling-id1|
%\g Or when a crusty Stirling problem needs to be polished off, like
%Stirling silver.\g
and |stirling-id2| contain the formulas that are most frequently useful;
the principal identities we have already derived are repeated there.

When we studied binomial coefficients in Chapter~5, we found that it was
advantageous to define $n\choose k$ for negative~$n$ in such a way that
the identity ${n\choose k}={n-1\choose k}+{n-1\choose k-1}$ is valid without
any restrictions. Using that identity to extend the
$n\choose k$'s beyond those with combinatorial significance,
we discovered (in Table~|pascal-triangle-up|) that Pascal's
triangle essentially reproduces itself in a rotated form when we
extend it upward. Let's try the same thing with "Stirling's triangles": What
happens if we decide that the basic recurrences
\begindisplay \openup5pt \advance\abovedisplayskip-3pt
{n\brace k}&=k@{n-1\brace k}+{n-1\brace k-1}\cr
{n\brack k}&=(n-1){n-1\brack k}+{n-1\brack k-1}\cr
\enddisplay
are valid for all integers $n$ and $k$? The solution becomes unique if we
make the reasonable additional stipulations that
\begindisplay
{0\brace k}={0\brack k}=\[k=0]\And {n\brace0}={n\brack0}=\[n=0]\,.
\eqno
\enddisplay
In fact, a surprisingly pretty pattern emerges:
Stirling's triangle for cycles appears above Stirling's triangle for subsets,
and vice versa! The two kinds of Stirling numbers are
related by an extremely simple law [|knuth-tnn|, |knuth-cp|]:
\begindisplay\advance\abovedisplayskip-3pt\advance\belowdisplayskip-3pt
{@n@\brack k}={-k\brace-n}\,,\qquad\hbox{integers $k,n$}.
\eqno\eqref|stirl-negation|
\enddisplay
We have ``"duality",\qback'' something like the relations between min and max,
between $\lfloor x \rfloor$ and~$\lceil x\rceil$, between $x\_n$
and~$x\_^n$, between gcd and lcm. It's easy to check that both of the recurrences
${n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1}$ and
${n\brace k}=k{n-1\brace k}+{n-1\brace k-1}$ amount to the same thing, under
this correspondence.

\topinsert
\setbox0=\hbox{$\biggr\}$}
\def\\#1{\displaystyle{n\brace#1}\kern-\wd0}
\table Stirling's triangles in tandem.\tabref|stirl-triangles|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\{-5}&\\{-4}&\\{-3}&\\{-2}&\\{-1}&\\0&\\1&\\2&\\3&\\4&\\5\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
-5&& 1 \cr
-4&& 10 & 1 \cr
-3&& 35 & 6 & 1 \cr
-2&& 50 & 11 & 3 & 1 \cr
-1&& 24 & 6 & 2 & 1 & 1 \cr
0 && 0 & 0 & 0 & 0 & 0 & 1 \cr
1 && 0 & 0 & 0 & 0 & 0 & 0 & 1 \cr
2 && 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \cr
3 && 0 & 0 & 0 & 0 & 0 & 0 & 1 & 3 & 1 \cr
4 && 0 & 0 & 0 & 0 & 0 & 0 & 1 & 7 & 6 & 1 \cr
5 && 0 & 0 & 0 & 0 & 0 & 0 & 1 & 15 & 25 & 10 & 1 \ \cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

\beginsection 6.2 Eulerian Numbers

Another triangle of values pops up now and again, this one due to "Euler"
[|euler-eulerian|, \S13; |euler-diff-calc|, page 485],
 and we denote its
elements by $n\euler k$. The angle brackets in this case suggest
``less than'' and ``greater than'' signs; $n\euler k$ is the number of
permutations $\pi_1\pi_2\ldots\pi_n$ of $\{1,2,\ldots,n\}$ that
have $k$ {\it"ascents"}, namely, $k$~places where $\pi_j<\pi_{j+1}$.
"!descents, \string\see ascents"
"!notation, new"
(Caution: This notation is less standard than our notations
\g(Knuth [|knuth3|, first edition] used\smallskip
 $n\euler k+1$ for $n\euler k$.)\g
\tabref|nn:euler|%
$n\brack k$, $n\brace k$ for Stirling numbers. But we'll see that it makes good
sense.)