   Various combinatorial numbers

### Various combinatorial numbers

These considerations lead to various combinatorial numbers so that a few remarks concerning these are in order. For example, YXs,g is the set of surjective mappings f ÎYX which are constant on the c( bar (g)) cyclic factors of bar (g). Hence this set can be identified with the set Ys c( bar (g)) . More generally we consider the set ms n and define the numbers S(n,m) by
m!S(n,m):= | m ns | , where m,n Î N.
These S(n,m) are called the Stirling numbers of the second kind . If n is used as row index and m as column index, then the upper left hand corner of the table of Stirling numbers of the second kind is as follows:
 1 0 1 0 1 1 0 1 3 1 0 1 7 6 1 0 1 15 25 10 1 ... ...
There is a program for computing the stirling second numbers.

By definition m!S(n,m) is equal to the number of ordered set partitions   ( n(1), ..., n (m)) of n into m blocks, i.e. into m nonempty subsets n(i). This is clear since each such ordered partition can be identified with f : n -> m where f-1[ {i }]:= n(i), i Î m. Thus S(n,m) is the number of set partitions { n(1), ..., n(m) } of the set n into m blocks, and hence Bn, the number of all the set partitions of n satisfies the equation

Bn= åk=0nS(n,k).
These numbers Bn 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 of Corollary is

| Y | !S(c( bar (g)), | Y | )= | Ys,gX | = åk=1 | Y | (-1) | Y | -k[ | Y | choose k]kc( bar (g)),
which implies:
Stirling's Formula For m>0 and any natural number n we have:
S(n,m)=(1)/(m!) åk=1m(-1)m-k[m choose k]kn.
Another series of combinatorial numbers shows up if we rewrite Theorem in the following form:
| G \\YsX | =( | Y | !)/( | G | ) åk=1 | X | S(k, | Y | ) | {g ÎG | c( bar (g)) =k } | .
We put
r(n,k):= | { pÎS n | c( p)=k } | ,
and call these the signless Stirling numbers of the first kind. They satisfy the following recursion formula, since in pÎSn the point n either forms a 1-cycle or does not:
Lemma: For n,k >1 we have
r(n,k)=r(n-1,k-1)+(n-1)r(n-1,k)
while the initial values are r(0,0)=1 and r(n,0)=r(0,k)=0, for n,k>0.
The upper left hand corner of a table containing these numbers r(n,k), for n,k Î N, is as follows
 1 0 1 0 1 1 0 2 3 1 0 6 11 6 1 0 24 50 35 10 1 ... ...
There is a program for computing the stirling first numbers.

We now return to the number | SX \\YXs | . The exercise together with the identity yields

( | Y | !)/( | X | !) åk=1 | X | r( | X | ,k)S(k, | Y | ) = [ | X | -1 choose | Y | -1].
Another series of combinatorial numbers arises when we count certain injective symmetry classes, since Theorem implies
| SY \\YiX | =( | X | !)/( | Y | !) åk= | X | | Y | t( | Y | ,k) [k choose | X | ],
where t(n,k):= | { pÎS n | a1( p)=k } | . It is easy to derive these numbers from the rencontre numbers   R(n):= t(n,0), since obviously the following is true:
t(n,k)=[n choose k]R(n-k).
This can be made more explicit by an application of exercise which yields
R(n)=n! åk=0n((-1)k)/(k!).
There is a program for computing the recontre numbers and their generalization.

Now we use that, for | Y | >= | X | , | SY \\YXi | =1, so that by the last three equations:

1= åk= | X | | Y | (1)/((k- | X | )!) åj=0 | Y | -k((-1)j)/(j!), if | Y | >= | X | .
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 n and k the following identities hold:
åm=1k[k choose m][n-1 choose m-1]=[n+k-1 choose n] =(1)/(n!) å pÎS nkc( p).
Proof: Exercise implies that, for m <= k,
[k choose m][n-1 choose m-1]
is equal to the number of symmetry classes of Sn on k n, the elements of which satisfy | f[ n] | =m. Thus the left hand side is | Sn \\ k n | . But the orbit of f Î kn under Sn is characterized by the orders of the inverse images | f-1[ {i }] | , i Î k. Hence the number of these orbits is equal to the number of k-tupels (n1, ..., nk), ni Î N, and åni=n, therefore the first identity follows from exercise. The last equation is already clear from Theorem.
harald.fripertinger@kfunigraz.ac.at,
last changed: August 28, 2001   Various combinatorial numbers