Stirling numbers of the second kind

( 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 */