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, Y^X_s,g is the set of surjective mappings f ÎY^X which are constant on the c( bar (g)) cyclic factors of bar (g). Hence this set can be identified with the set Y_s ^{c( bar (g))} . More generally we consider the set m_s ⁿ and define the numbers S(n,m) by

m!S(n,m):= | m ⁿ_s | , 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⁽¹⁾, ..., n ^(m)) of n into m blocks, i.e. into m nonempty subsets n⁽ⁱ⁾. This is clear since each such ordered partition can be identified with f : n -> m where f^-1[ {i }]:= n⁽ⁱ⁾, i Î m. Thus S(n,m) is the number of set partitions { n⁽¹⁾, ..., n^(m) } of the set n into m blocks, and hence B_n, the number of all the set partitions of n satisfies the equation

  B_n= å_k=0ⁿS(n,k).

These numbers B_n 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 | )= | Y_s,g^X | = å_k=1 ^{| Y |} (-1) ^{| Y | -k}[ | Y | choose k]k^{c( bar (g))},

which implies:

Stirling's Formula For m>0 and any natural number n we have:

S(n,m)=(1)/(m!) å_k=1^m(-1)^m-k[m choose k]kⁿ.

Another series of combinatorial numbers shows up if we rewrite Theorem in the following form:

| G \\Y_s^X | =( | 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ÎS_n 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 | S_X \\Y^X_s | . 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

  | S_Y \\Y_i^X | =( | X | !)/( | Y | !) å_{k= | X |} ^{| Y |} t( | Y | ,k) [k choose | X | ],

where t(n,k):= | { pÎS _n | a₁( 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=0ⁿ((-1)^k)/(k!).

There is a program for computing the recontre numbers and their generalization.

Now we use that, for | Y | >= | X | , | S_Y \\Y^X_i | =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=1^k[k choose m][n-1 choose m-1]=[n+k-1 choose n] =(1)/(n!) å _{pÎS n}k^{c( 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 S_n on k ⁿ, the elements of which satisfy | f[ n] | =m. Thus the left hand side is | S_n \\ k ⁿ | . But the orbit of f Î kⁿ under S_n 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 (n₁, ..., n_k), n_i Î N, and ån_i=n, therefore the first identity follows from exercise. The last equation is already clear from Theorem.

Various combinatorial numbers