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

m!S(n,m):= |m^{ n}_{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^{(1)}, ..., n
^{(m)})* of

B_{n}= å_{k=0}^{n}S(n,k).

These numbers *B _{n}* are called

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 FormulaForm>0and any natural numbernwe have:S(n,m)=(1)/(m!)å_{k=1}^{m}(-1)^{m-k}[m choose k]k^{n}.

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

Lemma:Forn,k >1we havewhile the initial values arer(n,k)=r(n-1,k-1)+(n-1)r(n-1,k)r(0,0)=1andr(n,0)=r(0,k)=0, forn,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_{1}( p)=k } | *.
It is easy to derive these numbers from the

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}^{n}((-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 numbersnandkthe 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

harald.fripertinger "at" uni-graz.at | http://www-ang.kfunigraz.ac.at/~fripert/ |

UNI-Graz | Institut für Mathematik |

UNI-Bayreuth | Lehrstuhl II für Mathematik |

Various combinatorial numbers |