Distributing Balls into Boxes

Here, we are counting the number of ways in which k balls can be distributed into n boxes under various conditions.

The conditions which are generally asked are

1. The balls are either distinct or identical.
2. The boxes are either distinct or identical.
3. No box can contain more than one ball or any box may contain more than one ball.
4. No box can be empty or any box can be empty.

The concept of identical boxes are more complicated and generally studied in detail in combinatorics.

The table below explains the number of ways in which k balls can be distributed into n boxes under various conditions. All the below mentioned cases are derived under the assumption that the order in which the balls are placed into the boxes is not important. (i.e., if a box has many balls, the order of the balls inside the box is not important).

$\text{S(k,n)}=\frac{1}{n!}\sum _{i=0}^{n-1}{(-1)}^i{n}_{C_i}(n-i{)}^k$
$=\frac{1}{n!}\left[n_{C_0}\right(n-0{)}^k-n_{C_1}(n-1{)}^k$ $+n_{C_2}(n-2{)}^k+\cdots +{(-1)}^{n-1}{n}_{C_{n-1}}(1{)}^k]$

Special Cases
S(0,0) = 1
S(k,0) = 0 for k ≥ 1
S(k,n) = 0 for k < n

P(k,n) = The number of partitions of the integer k into n parts.