The Balls in Boxes is a more complex model. The goal is to find the number of ways to put $k$ balls into $n$ boxes. Depending on the following factors, there are totally $8$ variations with significant differences in complexity:
- Whether or not the balls are distinguishable
- Whether or not the boxes are distinguishable
- Whether or not empty boxes are permitted
Counting the number of integer solutions to $x_1+x_2+\cdots + x_k=n$ is equivalent to the case where balls are indistinguishable but boxes are distinguishable. If no empty box is permitted, then all $x_i$ must be positive, otherwise they are non-negative. See assignment (#4769).
The following diagram is a summary of all these $8$ cases and their correspoding solutions. Usually, only the first two rows may be tested. When problems in other categories arise, they usually involve small numbers and thus can be manually computed.
The difference between distinguishable and indistinguishable is whether these objects are swappable, i.e. whether or not their order matters. If swapping two objects does not impact the result, then they are indistinguishable. Otherwise, they are distinguishable.