Editing Inclusion–exclusion principle (section)

===Stirling numbers of the second kind===
{{main|Stirling numbers of the second kind}}

The [[Stirling numbers of the second kind]], ''S''(''n'',''k'') count the number of [[Partition of a set|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 set|ordered]] non-empty subsets). Using the universal set consisting of all partitions of the ''n''-set into ''k'' (possibly empty) distinguishable boxes, ''A''<sub>1</sub>, ''A''<sub>2</sub>, ..., ''A<sub>k</sub>'', and the properties ''P<sub>i</sub>'' meaning that the partition has box ''A<sub>i</sub>'' 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:<ref>{{harvnb|Brualdi|2010|loc=pp. 282&ndash;7}}</ref>

:<math>S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.</math>