Various combinatorial numbers |

Thesem!S(n,m):= |m^{ n}_{s}| , where m,n ÎN.

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

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

Another consequence of the definition of Stirling numbers of the second kind and of Corollary is

which implies:| Y | !S(c( bar (g)), | Y | )= | Y_{s,g}^{X}| = å_{k=1}^{ | Y | }(-1)^{ | Y | -k}[ | Y | choose k]k^{c( bar (g))},

Another series of combinatorial numbers shows up if we rewrite Theorem in the following form:Stirling's FormulaForm>0and any natural numbernwe have:S(n,m)=(1)/(m!)å_{k=1}^{m}(-1)^{m-k}[m choose k]k^{n}.

We put| G \\Y_{s}^{X}| =(| Y | !)/(| G |)å_{k=1}^{ | X | }S(k, | Y | ) | {g ÎG | c( bar (g)) =k } | .

and call these ther(n,k):= | { pÎS_{ n}| c( p)=k } | ,

The upper left hand corner of a table containing these numbersLemma: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.

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 * | S _{X} \\Y^{X}_{s} | *.
The exercise
together with the identity yields

Another series of combinatorial numbers arises when we count certain injective symmetry classes, since Theorem implies(| Y | !)/(| X | !)å_{k=1}^{ | X | }r( | X | ,k)S(k, | Y | ) = [ | X | -1 choose | Y | -1].

where| S_{Y}\\Y_{i}^{X}| =(| X | !)/(| Y | !)å_{k= | X | }^{ | Y | }t( | Y | ,k) [k choose | X | ],

This can be made more explicit by an application of exercise which yieldst(n,k)=[n choose k]R(n-k).

There is a program for computing the recontre numbers and their generalization.R(n)=n! å_{k=0}^{n}((-1)^{k})/(k!).

Now we use that, for * | Y | >= | X | , | S _{Y} \\Y^{X}_{i} | =1*, 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 identity1= å_{k= | X | }^{ | Y | }(1)/((k- | X | )!)å_{j=0}^{ | Y | -k}((-1)^{j})/(j!), if | Y | >= | X | .

Proof: Exercise implies that, forLemma: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)}.

is equal to the number of symmetry classes of[k choose m][n-1 choose m-1]

harald.fripertinger@kfunigraz.ac.at,

last changed: August 28, 2001

Various combinatorial numbers |