These considerations lead to various combinatorial numbers
so that a few
remarks concerning these are in order. For example, 
is the set
of surjective mappings 
which are constant on the 
cyclic factors of 
. Hence this set can be identified with
the set 
.
More generally we consider the set
and define the numbers
by
These are called the Stirling numbers
of the second
kind . If 
is used as row index and 
as column index, then the upper
left hand corner of the table of Stirling numbers of the second kind is as
follows:
There is a program for computing the stirling second numbers.
By definition
is equal
to the number of ordered set partitions
of 
into blocks,
i.e. into nonempty subsets 
.
This is clear since each such ordered partition
can be identified with 
where 
. Thus
is the number of set partitions
of the set
into blocks, and
hence 
, the number of all the set partitions of 
satisfies
the equation
These numbers are called Bell numbers .
There is a program for
computing the Bell numbers.
Another consequence
of the definition of Stirling numbers of the second kind and 
is
which implies:
.
Stirling's Formula
For 
and any natural number
we have:
Another series of combinatorial numbers shows up if we rewrite in
the following form:
We put
and call these the signless
Stirling numbers of the first kind.
They satisfy the following recursion formula, since in 
the point either forms a 1-cycle or does not:
while the initial values are 
.
Lemma For 
we have
and 
, for 
.
The upper left hand corner of a table containing
these numbers 
, for
, is as follows
There is a program for computing the stirling first numbers.
We now return to the number 
. The exercise
together with the identity yields
Another series of combinatorial numbers arises when we count certain injective
symmetry classes,
since implies
where 
.
It is easy to derive these numbers from the rencontre numbers
, since obviously the following is true:
This can be made more explicit by an application of exercise
which yields
There is a program for computing the recontre numbers and their generalization.
Now we use that, for 
, so that by the last three equations:
It is in fact an important and interesting task of enumeration theory to derive identities in this way since they are understood as soon as they are seen to describe a combinatorial situation. Another example is the identity
.
Lemma For natural numbers and 
the following
identities hold:
Proof: Exercise implies
that, for 
,
is equal to the number of symmetry classes of 
on
, the elements of which satisfy
. Thus
the left hand side is 
. But
the orbit of 
under is characterized by the orders
of the inverse images 
. Hence the
number of these orbits is equal to the number of -tupels 
, and 
, therefore
the first identity follows from
exercise . The last
equation is already clear
from .
Exercises
E 
.
Use the Principle of Inclusion and Exclusion in order to prove .
E 
.
Show that the number of -tupels 
such that
and is equal to
E 
.
Prove that the Stirling numbers of the second kind satisfy the equation
where 
