chap6.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 6 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib

\pageno=257 % Please begin on right-hand page (we want tables on facing pages)
\refin chap2
\refin chap4
\refin chap5
\refin chap7
\refin chap9

\beginchapter 6 Special Numbers

SOME SEQUENCES of "numbers" arise so often in mathematics that we recognize them
instantly and give them special names.
For example, everybody who learns arithmetic knows the sequence
of square numbers $\langle 1,4,9,16,\ldots\,\rangle$.
In Chapter~1 we encountered
the triangular numbers $\langle 1,3,6,10,\ldots\,\rangle$;
in Chapter~4 we studied
the prime numbers $\langle 2,3,5,7,\ldots\,\rangle$;
in Chapter~5 we looked briefly at
the Catalan numbers $\langle 1,2,5,14,\ldots\,\rangle$.

In the present chapter we'll get to know a few other important sequences.
First on our agenda will be the Stirling numbers $n\brace k$ and
$@n@\brack k$, and the Eulerian numbers $n\euler k$; these form triangular
patterns of coefficients analogous to the binomial coefficients $n\choose k$
in Pascal's triangle.
Then we'll take a good look at the harmonic numbers~$H_n$, and
%a quick glance at
the Bernoulli numbers~$B_n$; these differ from the other sequences we've been
studying because they're fractions, not integers.
Finally, we'll examine the fascinating Fibonacci numbers~$F_n$ and some
of their important generalizations.

\beginsection 6.1 Stirling Numbers

We begin with some close relatives of the binomial coefficients, the
"Stirling numbers", named after James "Stirling" (1692--1770). These numbers
come in two flavors, traditionally called by the no-frills names
``Stirling numbers of the first and second kind.\qback''
Although they have a venerable history and numerous applications, they
still lack a standard "notation". Following Jovan "Karamata",
\g\noindent\llap{``}\dots\ par cette notation, les formules deviennent plus sym\'etriques.''
\par\hfill\hskip0pt minus5pt\dash---J.~"Karamata"~[|karamata|]\g
we will write $n\brace k$ for Stirling
numbers of the second kind and $@n@\brack k$ for Stirling numbers
of the first kind; these symbols turn out to be more
user-friendly than the many other notations that people have tried.

Tables |stirl2-triangle| and |stirl1-triangle| show what
$n\brace k$ and~$@n@\brack k$ look like when $n$ and~$k$ are small.
A problem that involves the numbers 
``$1$, $7$, $6$,~$1$'' is likely to be related to $n\brace k$,
 and a problem that involves
``$6$, $11$, $6$,~$1$'' is
likely to be related to $@n@\brack k$,
just as we assume that a problem involving ``$1$, $4$, $6$, $4$, $1$''
is likely to be related to $n\choose k$;
these are the trademark sequences that appear when $n=4$.

\topinsert
\setbox0=\hbox{$\biggr\}$}
\def\\#1{\displaystyle{n\brace#1}\kern-\wd0}
\table Stirling's triangle for subsets.\tabref|stirl2-triangle|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\0&\\1&\\2&\\3&\\4&\\5&\\6&\\7&\\8&\\9\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
0 && 1 \cr
1 && 0 & 1 \cr
2 && 0 & 1 & 1 \cr
3 && 0 & 1 & 3 & 1 \cr
4 && 0 & 1 & 7 & 6 & 1 \cr
5 && 0 & 1 & 15 & 25 & 10 & 1 \cr
6 && 0 & 1 & 31 & 90 & 65 & 15 & 1 \cr
7 && 0 & 1 & 63 & 301 & 350 & 140 & 21 & 1 \cr
8 && 0 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 \cr
9 && 0 & 1 & \ 255 & 3025 & 7770 & 6951 & 2646 & 462 & 36 & 1 \ \cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

Stirling numbers of the second kind show up more often than those of
the other variety, so let's consider last things first. The symbol $n\brace k$
\g("Stirling" himself considered this kind first in his book~[|stirling-method|].)\g
\tabref|nn:brace|%
stands for the number of ways to "partition a set" of $n$~things into
$k$~nonempty subsets. For example, there are seven ways to split
a four-element set into two parts:
\begindisplay
&\{1,2,3\}\cup\{4\}\,,\qquad
\{1,2,4\}\cup\{3\}\,,\qquad
\{1,3,4\}\cup\{2\}\,,\qquad
\{2,3,4\}\cup\{1\}\,,\cr
&\{1,2\}\cup\{3,4\}\,,\qquad
\{1,3\}\cup\{2,4\}\,,\qquad
\{1,4\}\cup\{2,3\}\,;
\eqno\eqref|stirl2-42|
\enddisplay
thus ${4\brace2}=7$. Notice that curly braces are used to denote sets
as well as the numbers $n\brace k$. This notational
kinship helps us remember the meaning
of $n\brace k$, which can be read ``$n$~subset~$k$.\qback''

Let's look at small~$k$.
There's just one way to put $n$ elements into a single nonempty set;
hence ${n\brace1}=1$, for all $n>0$. On the other hand ${0\brace1}=0$,
because a $0$-element set is empty.
%In general we have ${n\brace k}=0$ whenever $n<k$.

The case $k=0$ is a bit tricky. Things work out best if we agree that there's
just one way to partition an empty set into zero nonempty parts; hence
${0\brace0}=1$. But a nonempty set needs at least one part,
 so ${n\brace0}=0$ for $n>0$.

What happens when $k=2$? Certainly ${0\brace2}
=0$. If a set of $n>0$ objects is divided into two nonempty
parts, one of those parts contains the last object and some subset
of the first $n-1$~objects. There are $2^{n-1}$ ways to choose the
latter subset,
since each of the first $n-1$~objects is either in it or out of~it;
but we mustn't put all of those objects in~it, because we want to
end up with two nonempty parts. Therefore we subtract~$1$:
\begindisplay
{n\brace2}=2^{n-1}-1\,,\qquad\hbox{integer $n>0$}.
\eqno
\enddisplay
(This tallies with our enumeration of ${4\brace2}=7=2^3-1$ ways above.)

\topinsert
\setbox0=\hbox{$\biggr]$}
\def\\#1{\displaystyle{n\brack#1}\kern-\wd0}
\table Stirling's triangle for cycles.\tabref|stirl1-triangle|
\offinterlineskip
\halign to\hsize{\strut$\hfil#$\quad&\vrule#\kern-5pt\tabskip10pt plus 100pt&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$&
 \hfil$#$\tabskip\wd0\cr
\omit&height 3pt\cr
n &&\\0&\\1&\\2&\\3&\\4&\\5&\\6&\\7&\\8&\\9\cr
\omit&height 2pt\cr
\noalign{\hrule width\hsize}
\omit&height 3pt\cr
0 && 1 \cr
1 && 0 & 1 \cr
2 && 0 & 1 & 1 \cr
3 && 0 & 2 & 3 & 1 \cr
4 && 0 & 6 & 11 & 6 & 1 \cr
5 && 0 & 24 & 50 & 35 & 10 & 1 \cr
6 && 0 & 120 & 274 & 225 & 85 & 15 & 1 \cr
7 && 0 & 720 & 1764 & 1624 & 735 & 175 & 21 & 1 \cr
8 && 0 & 5040 & 13068 & 13132 & 6769 & 1960 & 322 & 28 & 1 \cr
9 && 0 & 40320 & 109584 & 118124 & 67284 & 22449 & 4536 & 546 & \ 36 & 1 \ \cr
\omit&height 2pt\cr}
\hrule width\hsize height.5pt
\kern4pt
\endinsert

\goodbreak
A modification of this argument leads to a recurrence by which we can
compute $n\brace k$ for all~$k@$: Given a set of $n>0$ objects to be
partitioned into $k$ nonempty parts, we either put the last object
into a class by itself (in $n-1\brace k-1$ ways), or we put it together
with some nonempty subset of the first $n-1$ objects. There are $k{n-1\brace k}$
possibilities in the latter case, because each of the $n-1\brace k$ ways
to distribute the first $n-1$ objects into $k$~nonempty parts gives $k$~subsets
that the $n$th object can join. Hence
\begindisplay
{n\brace k}=k@{n-1\brace k}+{n-1\brace k-1}\,,
\qquad\hbox{integer $n>0$}.
\eqno\eqref|stirl2-rec|
\enddisplay
This is the law that generates Table |stirl2-triangle|; without the factor
of~$k$ it would reduce to the addition formula \equ(5.|bc-addition|)
that generates Pascal's triangle.

\smallbreak
And now, "Stirling numbers of the first kind". These are somewhat
like the others, but $n\brack k$ counts the number of ways to arrange $n$~objects
\tabref|nn:brack|%
into $k$ {\it"cycles"\/} instead of subsets. We verbalize
`$n\brack k$' by saying ``$n$~cycle~$k$.\qback''

Cycles are cyclic arrangements, like the "necklace"s we considered in
Chapter~4. The "cycle"
\begindisplay \advance\belowdisplayskip -3pt
\unitlength=1pt
\def\necklace#1#2#3#4{\beginpicture(30,30)(-15,-15)%
 \ovaltlfalse\ovaltrfalse\ovalblfalse\ovalbrfalse
 {\ovaltrtrue\put(5,6){\oval(12,12)}}%
 {\ovaltltrue\put(-5,6){\oval(12,12)}}%
 {\ovalbltrue\put(-5,-6){\oval(12,12)}}%
 {\ovalbrtrue\put(5,-6){\oval(12,12)}}%
 \put(0,12){\makebox(0,0){$#1$}}%
 \put(11,0){\makebox(0,0){$#2$}}%
 \put(0,-12){\makebox(0,0){$#3$}}%
 \put(-11,0){\makebox(0,0){$#4$}}%
 \endpicture}
\kern2pt\necklace ABC{D\kern2pt}
\enddisplay
can be written more compactly as `$[A,B,C,D]$', with the understanding that
\begindisplay
[A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\,;
\enddisplay
a cycle ``wraps around'' because its end is joined to its beginning.
On the other hand, the cycle
$[A,B,C,D]$ is not the same as $[A,B,D,C]$ or $[D,C,B,A]$.

There are eleven different ways
\g\noindent\llap{``}There are nine and~sixty ways\par of constructing tribal lays,\par
And-every-single-one-of-them-is-right.''\par\hfill\dash---Rudyard "Kipling"\g
to make two cycles from four elements:
\begindisplay
&[1,2,3]\,[4]\,,\qquad
[1,2,4]\,[3]\,,\qquad
[1,3,4]\,[2]\,,\qquad
[2,3,4]\,[1]\,,\cr
&[1,3,2]\,[4]\,,\qquad
[1,4,2]\,[3]\,,\qquad
[1,4,3]\,[2]\,,\qquad
[2,4,3]\,[1]\,,\cr
&[1,2]\,[3,4]\,,\qquad
[1,3]\,[2,4]\,,\qquad
[1,4]\,[2,3]\,;
\eqno\eqref|stirl1-42|
\enddisplay
hence ${4\brack2}=11$.

A singleton cycle (that is, a cycle with only one element) is essentially
the same as a singleton set (a set with only one element). Similarly,
a $2$-cycle "!bicycling (goes under sports too)"
is like a $2$-set, because we have $[A,B]=[B,A]$ just as $\{A,B\}=
\{B,A\}$. But there are two {\it different\/} $3$-cycles, $[A,B,C]$ and $[A,C,B]$.
Notice, for example, that the eleven cycle pairs in \thiseq\ can be obtained
from the seven set pairs in \eq(|stirl2-42|) by making two cycles from each
of the $3$-element sets.

In general, $n!/n=(n-1)!$ different $n$-cycles
 can be made from any $n$-element set, whenever
$n>0$. (There are $n!$ permutations, and each $n$-cycle corresponds to~$n$
of them because any one of its elements can be listed first.)
Therefore we have
\begindisplay
{n\brack1}=(n-1)!\,,\qquad\hbox{integer $n>0$}.
\eqno
\enddisplay
This is much larger than the value ${n\brace1}=1$ we had for Stirling
subset numbers. In fact, it is easy to see that the
cycle numbers must be at least as large as the subset numbers,
\begindisplay
{n\brack k}\ge{n\brace k}\,,\qquad\hbox{integers $n,k\ge0$},
\eqno
\enddisplay
because every partition into nonempty subsets leads to at least one
arrangement of cycles.

Equality holds in \thiseq\ when all the cycles are necessarily singletons
or doubletons, because cycles are equivalent to subsets in such cases.
This happens when $k=n$ and when $k=n-1$; hence
\begindisplay
{n\brack n}={n\brace n}\,;\qquad{n\brack n-1}={n\brace n-1}\,.
\enddisplay
In fact, it is easy to see that
\begindisplay
{n\brack n}={n\brace n}=1\,;\qquad{n\brack n-1}={n\brace n-1}={n\choose2}\,.
\eqno\eqref|stirl-nn-1|
\enddisplay
(The number of ways to arrange $n$ objects into $n-1$ cycles or subsets is
the number of ways to choose the two objects that will be in the same
cycle or subset.) The triangular numbers ${n\choose2}=1$, $3$, $6$,~$10$,
\dots\ are conspicuously present in both Table |stirl2-triangle| and Table
|stirl1-triangle|.

We can derive a recurrence for $n\brack k$ by modifying the argument we
used for~$n\brace k$. Every arrangement of $n$~objects in $k$~cycles
either puts the last object into a cycle by itself (in $n-1\brack k-1$ ways)
or inserts that object into one of the $n-1\brack k$ cycle arrangements
of the first $n-1$ objects. In the latter case, there are $n-1$ different
ways to do the insertion. (This takes some thought, but it's not hard
to verify that there are $j$ ways to put a new element into a
$j$-cycle in order to make a $(j+1)$-cycle. When $j=3$, for example,
the cycle $[A,B,C]$ leads to
\begindisplay
[A,B,C,D]\,,\qquad
[A,B,D,C]\,,\qquad\hbox{or}\qquad
[A,D,B,C]
\enddisplay
when we insert a new element $D$, and there are no other possibilities.
Summing over all $j$ gives a total of $n-1$ ways to insert an $n$th object
into a cycle decomposition of $n-1$ objects.)
The desired recurrence is therefore
\begindisplay
{n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1}\,,