In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. The idea of the classification is credited to Gian-Carlo Rota. The name was proposed by Joel Spencer.
Overview Let N and X be finite sets. Let n = | N | {\displaystyle n=|N|} and x = | X | {\displaystyle x=|X|} be the cardinalities of the sets. Thus N is a set with n elements, and X is a set with x elements. The general problem we consider is the enumeration of equivalence classes of functions f : N → X {\displaystyle f:N\to X} . The functions are subject to one of the three following restrictions:
No condition: each a in N may be sent by f to any b in X, and each b may occur multiple times. f is injective: each value f ( a ) {\displaystyle f(a)} for a in N must be distinct from every other, and so each b in X may occur at most once in the image of f. f is surjective: for each b in X there must be at least one a in N such that f ( a ) = b {\displaystyle f(a)=b} , thus each b will occur at least once in the image of f. (The condition "f is bijective" is only an option when n = x {\displaystyle n=x} ; but then it is equivalent to both "f is injective" and "f is surjective".) There are four different equivalence relations which may be defined on the set of functions f from N to X:
equality; equality up to a permutation of N; equality up to a permutation of X; equality up to permutations of N and X. The three conditions on the functions and the four equivalence relations can be paired in 3 × 4 = 12 ways. The twelve problems of counting equivalence classes of functions do not involve the same difficulties, and there is not one systematic method for solving them. Two of the problems are trivial (the number of equivalence classes is 0 or 1), five problems have an answer in terms of a multiplicative formula of n and x, and the remaining five problems have an answer in terms of combinatorial functions (Stirling numbers and the partition function for a given number of parts). The incorporation of classical enumeration problems into this setting is as follows.
Counting n-permutations (i.e., partial permutations or sequences without repetition) of X is equivalent to counting injective functions N → X. Counting n-combinations of X is equivalent to counting injective functions N → X up to permutations of N. Counting permutations of the set X is equivalent to counting injective functions N → X when n = x, and also to counting surjective functions N → X when n = x. Counting multisets of size n (also known as n-combinations with repetitions) of elements in X is equivalent to counting all functions N → X up to permutations of N. Counting partitions of the set N into x subsets is equivalent to counting all surjective functions N → X up to permutations of X. Counting compositions of the number n into x parts is equivalent to counting all surjective functions N → X up to permutations of N.
Viewpoints The various problems in the twelvefold way may be considered from different points of view.
Balls and boxes Traditionally many of the problems in the 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; the function f : N → X {\displaystyle f:N\to X} then describes a way to distribute the balls into the boxes, namely by putting each ball a into box f ( a ) {\displaystyle f(a)} . A function ascribes a unique image to each value in its domain; this property 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 an arbitrary number of balls. Requiring in addition f {\displaystyle f} to be injective means to forbid putting more than one ball in any one box, while requiring f {\displaystyle f} to be surjective means insisting that every box contain at least one ball. Counting modulo permutations of N or X is reflected by calling the balls or the boxes, respectively, "indistinguishable". This is an imprecise formulation, 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 or of boxes. This possibility of transformation is formalized by the action by permutations.
… excerpt ends here. Continue reading the full article.
