Twelvefold Way - Balls and Boxes

Balls and Boxes

Traditionally many of the problems in twelvefold way have been formulated in terms of placing balls in boxes (or some similar visualization) instead of defining functions. The set N can be identified with a set of balls, and X with a set of boxes; then function ƒ : N → X then describes a way to distribute the balls into the boxes, namely by putting each ball b into box ƒ(b). Thus the property that a function ascribes a unique image to each value in its domain is reflected by the property that any ball can go into only one box (together with the requirement that no ball should remain outside of the boxes), whereas any box can accommodate (in principle) an arbitrary number of balls. Requiring in addition ƒ to be injective means forbidding to put more than one ball in any one box, while requiring ƒ to be surjective means insisting that every box contain at least one ball.

Counting modulo permutations of N and/or of X is reflected by calling the balls respectively the boxes "indistinguishable". This is an imprecise formulation (in practice individual balls and boxes can always be distinguished by their location, and one could not assign different balls to different boxes without distinguishing them), intended to indicate that different configurations are not to be counted separately if one can be transformed into the other by some interchange of balls respectively of boxes; this is what the action by permutations of N and/or of X formalizes. In fact the case of indistinguishable boxes is somewhat harder to visualize than that of indistinguishable balls, since a configuration is inevitably presented with some ordering of the boxes; permuting the boxes will then appear as a permutation of their contents.