| | | Various combinatorial numbers |
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:
There is a program for computing the stirling second numbers.
1 0 1 0 1 1 0 1 3 1 0 1 7 6 1 0 1 15 25 10 1 ... ...
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:Another series of combinatorial numbers shows up if we rewrite Theorem in the following form:S(n,m)=(1)/(m!) åk=1m(-1)m-k[m choose k]kn.
| 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 haveThe upper left hand corner of a table containing these numbers r(n,k), for n,k Î N, is as followsr(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.
There is a program for computing the stirling first numbers.
1 0 1 0 1 1 0 2 3 1 0 6 11 6 1 0 24 50 35 10 1 ... ...
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:Proof: Exercise implies that, for m <= k,åm=1k[k choose m][n-1 choose m-1]=[n+k-1 choose n] =(1)/(n!) å pÎS nkc( p).
[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.
| | | Various combinatorial numbers |