( Repeat / memorized ) from Aigner, A course in enumeration.

Stirling numbers of the second kind: S(n,k).

Definition. S(n,k) is the number of k-partitions of an n-set.

Example:

{A}

S(1,1)=1

A

{A,B}

S(2,1)=1

AB

S(2,2)=1

A-B

{A,B,C}

S(3,1)=1

ABC

S(3,2)=3

A-BC

B-AC

C-AB

S(3,3)=1

A-B-C

Almost similar as for the number of combinations ( C(n,k)= C(n-1,k-1) + C(n-1,k) ) we can define the Stirling numbers of the second kind recursively:

S(n,k) = S(n-1,k-1) + k * S(n-1,k).

This recursion is easy to understand as we will see when we continue with the examples for {A,B,C,D}.

/* To be continued */

2-2018 Teaching by misleading

2 months ago

## No comments:

## Post a Comment