**Definition 8.6.8**
The Stirling number of the second kind,

,

is
defined as the number of partitions of

into exactly

non-empty subsets. Also

if

and

if

.

*Proof*.
Proof is by induction on

. It is clearly true when

, so take

and assume the result is true for

. Then