Stirling Number of the Second Kind

The number (read partition ) is the number of partitions of into nonempty parts, or equivalently, the number of equivalence relations of with equivalence classes

Theorem

Proof

We have two cases. If is an equivalence class, then there is other equivalence classes in This gives . Alternatively, if is in some other equivalence class, then there were ways to choose the other equivalence classes, and ways to add to one of them.

Theorem

Let be the Falling Factorial Then:

Proof 1

We can do induction on :

Proof 2

Suppose we are colouring the set into colours (where ) We can do this in ways. Each of those colourings uses colours. There is ways to partition the set into partitions, and then for each partition there is ways to assign different colours to the parts. Summing over each , we are done. Note that both LHS and RHS are polynomials of degree thus if they match on they have to match on

Theorem

Let be Rising Factorial Then:

Proof

Substitute in the previous theorem.

Theorem

Proof

Let have as its objects on just itself of weight .

Now counts ordered partitions of , and has Exponential Generating Function . But then the number of ordered partitions of is hence the result.

Theorem

The egf for cycles on with valutaion for

Proof 1

Proof 2

which implies