Conceptual numbers of stirling

Question

I keep reading about stirling numbers, but i cant understand the concept, can someone explain me what is a stirling number of species 1 and 2?

Answer 1

Consider the sequence

\begin{align*} x &= x \\ x(x-1) &= x^2 - x \\ x(x-1)(x-2) &= x^3 - 3x^2 - 2x \\ x(x-1)(x-2)(x-3) &= x^4 - 6x^3 + 11x^2 - 6 x \\ &\vdots \end{align*}

The coefficients of the multiplied-out polynomials,

1

-1, 1

-2, -3, 1

-6, 11, -6, 1

are the Sterling numbers of the first kind. There are usually a lot of ways of describing a simple process combinatorially, and multiplying out that product is no exception; each of these explanations gives a combinatorial interpretation of the Stirling numbers.

(Alternatively you could say that any one of these combinatorial interpretations is the definition, and that the thing about the polynomials above is an identity. Comes down to taste.)

The Stirling numbers of the second kind are similar but take a little longer to describe, so I'll refer you to Wikipedia.

Answer 2

$\newcommand{\s}{\,/\,}$The combinatorial meaning of Stirling numbers of the second kind can be explained easily: $S(n,k)$ is the number of partitions of a set of size $n$ into $k$ parts. For example, consider a set $\{a,b,c,d,e\}$ of five elements. $$ \begin{array}{lll} abcde & \text{1 partition into 1 part, so } S(5,1) = 1 \\[6pt] \left.\begin{array}{l} a\s bcde \\ b\s acde \\ c\s abde \\ d\s abce \\ e\s abcd \\ ab\s cde \\ ac\s bde \\ ad\s bce \\ ae\s bcd \\ bc\s ade \\ bd\s ace \\ be\s acd \\ cd\s abe \\ ce\s abd \\ de\s abc \end{array} \right\} & \text{15 partitions into 2 parts, so } S(5,2) = 15 \\[6pt] \left.\begin{array}{l} abc\s d\s e \\ abd\s c\s e \\ abe\s c\s d \\ acd\s b\s e \\ ace\s b\s d \\ ade\s b\s c \\ bcd\s a\s e \\ bce\s a\s d \\ bde\s a\s c \\ cde\s a\s b \\ ab\s cd\s e \\ ac\s bd\s e \\ ad\s bc\s e \\ ab\s ce\s d \\ ac\s be\s d \\ ae\s bc\s d \\ ab\s de\s c \\ ad\s be\s c \\ ae\s bd\s c \\ ac\s de\s b \\ ad\s ce\s b \\ ae\s cd\s b \\ bc\s de\s a \\ bd\s ce\s a \\ be\s cd\s a \end{array} \right\} & \text{25 partitions into 3 parts, so }S(5,3)=25 \\[6pt] \left.\begin{array}{l} ab\s c\s d\s e \\ ac\s b\s d\s e \\ ad\s b\s c\s e \\ ae\s b\s c\s d \\ bc\s a\s d\s e \\ bd\s a\s c\s e \\ be\s a\s c\s d \\ cd\s a\s b\s e \\ ce\s a\s b\s d \\ de\s a\s b\s c \end{array} \right\} & \text{10 partitions into 4 parts, so }S(5,4)=10 \\[6pt] a\s b\s c\s d\s e & \text{1 partition into 5 parts, so }S(5,5)=1 \end{array} $$