Inclusion–exclusion principle
Stirling numbers of the second kind

The Stirling numbers of the second kind, S (n, k) count the number of partitions of a set of n elements into k non-empty subsets (indistinguishable boxes). An explicit formula for them can be obtained by applying the principle of inclusion–exclusion to a very closely related problem, namely, counting the number of partitions of an n -set into k non-empty but distinguishable boxes (ordered non-empty subsets). Using the universal set consisting of all partitions of the n -set into k (possibly empty) distinguishable boxes, A, A,..., A, and the properties P meaning that the partition has box A empty, the principle of inclusion–exclusion gives an answer for the related result. Dividing by k ! to remove the artificial ordering gives the Stirling number of the second kind:
keywords:existence