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.Richard P. Stanley (1997). Enumerative Combinatorics, Volume I. Cambridge University Press. . p.41
Overview
Let and be finite sets. Let and be the cardinalities of the sets. Thus is a set with elements, and is a set with elements.
The general problem we consider is the enumeration of equivalence classes of functions .
The functions are subject to one of the three following restrictions: No condition: each in may be sent by to any in , and each may occur multiple times. is injective: each value for in must be distinct from every other, and so each in may occur at most once in the image of . is surjective: for each in there must be at least one in such that , thus each will occur at least once in the image of . (The condition " is bijective" is only an option when ; but then it is equivalent to both " is injective" and " is surjective".)
There are four different equivalence relations which may be defined on the set of functions from to : equality; equality up to a permutation of ; equality up to a permutation of ; equality up to permutations of and . The three conditions on the functions and the four equivalence relations can be paired in 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 and , 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 -permutations (i.e., partial permutations or sequences without repetition) of is equivalent to counting injective functions . Counting -combinations of is equivalent to counting injective functions up to permutations of . Counting permutations of the set is equivalent to counting injective functions when = , and also to counting surjective functions when . Counting multisets of size (also known as -combinations with repetitions) of elements in is equivalent to counting all functions up to permutations of . Counting partitions of the set into subsets is equivalent to counting all surjective functions up to permutations of . Counting compositions of the number into parts is equivalent to counting all surjective functions up to permutations of .
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 can be identified with a set of balls, and with a set of boxes; the function then describes a way to distribute the balls into the boxes, namely by putting each ball into box . 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 to be injective means to forbid putting 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 or 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.
Sampling
Another way to think of some of the cases is in terms of sampling, in statistics. Imagine a population of items (or people), of which we choose . Two different schemes are normally described, known as "sampling with replacement" and "sampling without replacement". In the former case (sampling with replacement), once we've chosen an item, we put it back in the population, so that we might choose it again. The result is that each choice is independent of all the other choices, and the set of samples is technically referred to as independent identically distributed. In the latter case, however, once we have chosen an item, we put it aside so that we can not choose it again. This means that the act of choosing an item has an effect on all the following choices (the particular item can not be seen again), so our choices are dependent on one another.
A second distinction among sampling schemes is whether ordering matters. For example, if we have ten items, of which we choose two, then the choice (4, 7) is different from (7, 4) if ordering matters; on the other hand, if ordering does not matter, then the choices (4, 7) and (7, 4) are equivalent.
The first two rows and columns of the table below correspond to sampling with and without replacement, with and without consideration of order. The cases of sampling with replacement are found in the column labeled "Any ", while the cases of sampling without replacement are found in the column labeled "Injective ". The cases where ordering matters are found in the row labeled "Distinct," and the cases where ordering does not matter are found in the row labeled " orbits". Each table entry indicates how many different sets of choices there are, in a particular sampling scheme. Three of these table entries also correspond to probability distributions. Sampling with replacement where ordering matters is comparable to describing the joint distribution of separate random variables, each with an -fold categorical distribution. Sampling with replacement where ordering does not matter, however, is comparable to describing a single multinomial distribution of draws from an -fold category, where only the number seen of each category matters. Sampling without replacement where ordering does not matter is comparable to a single multivariate hypergeometric distribution. Sampling without replacement where order does matter does not seem to correspond to a probability distribution.Robert V. Hogg and Elliot A. Tanis (2001). Probability and Statistical Inference. Prentice-Hall, Inc. . p.81 In all the injective cases (sampling without replacement), the number of sets of choices is zero unless . ("Comparable" in the above cases means that each element of the sample space of the corresponding distribution corresponds to a separate set of choices, and hence the number in the appropriate box indicates the size of the sample space for the given distribution.)
From the perspective of sampling, the column labeled "Surjective " is somewhat strange: Essentially, we keep sampling with replacement until we have chosen each item at least once. Then, we count how many choices we have made, and if it is not equal to , throw out the entire set and repeat. This is vaguely comparable to the coupon collector's problem, where the process involves "collecting" (by sampling with replacement) a set of coupons until each coupon has been seen at least once. In all surjective cases, the number of sets of choices is zero unless .
Labelling, selection, grouping
A function can be considered from the perspective of or of . This leads to different views:
the function labels each element of by an element of . the function selects (chooses) an element of the set for each element of , a total of choices. the function groups the elements of together that are mapped to the same element of .
These points of view are not equally suited to all cases. The labelling and selection points of view are not well compatible with permutation of the elements of , since this changes the labels or the selection; on the other hand the grouping point of view does not give complete information about the configuration unless the elements of may be freely permuted. The labelling and selection points of view are more or less equivalent when is not permuted, but when it is, the selection point of view is more suited. The selection can then be viewed as an unordered selection: a single choice of a (multi-)set of elements from is made.
Labelling and selection with or without repetition
When viewing as a labelling of the elements of , the latter may be thought of as arranged in a sequence, and the labels from as being successively assigned to them. A requirement that be injective means that no label can be used a second time; the result is a sequence of labels without repetition. In the absence of such a requirement, the terminology "sequences with repetition" is used, meaning that labels may be used more than once (although sequences that happen to be without repetition are also allowed).
When viewing as an unordered selection of the elements of , the same kind of distinction applies. If must be injective, then the selection must involve distinct elements of , so it is a subset of of size , also called an -combination. Without the requirement, one and the same element of may occur multiple times in the selection, and the result is a multiset of size of elements from , also called an -multicombination or -combination with repetition.
The requirement that be surjective, from the viewpoint of labelling elements of , means that every label is to be used at least once; from the viewpoint of selection from , it means that every element of must be included in the selection at least once. Labelling with surjection is equivalent to a grouping of elements of followed by labeling each group by an element of , and is accordingly somewhat more complicated to describe mathematically.
Partitions of sets and numbers
When viewing as a grouping of the elements of (which assumes one identifies under permutations of ), requiring to be surjective means the number of groups must be exactly . Without this requirement the number of groups can be at most . The requirement of injective means each element of must be a group in itself, which leaves at most one valid grouping and therefore gives a rather uninteresting counting problem.
When in addition one identifies under permutations of , this amounts to forgetting the groups themselves but retaining only their sizes. These sizes moreover do not come in any definite order, while the same size may occur more than once; one may choose to arrange them into a weakly decreasing list of numbers, whose sum is the number . This gives the combinatorial notion of a partition of the number , into exactly (for surjective ) or at most (for arbitrary ) parts.
Formulas Formulas for the different cases of the twelvefold way are summarized in the following table; each table entry links to a subsection below explaining the formula. + The twelve combinatorial objects and their enumeration formulas -class Any Injective Surjective Distinct -sequence in -permutation of composition of with subsets orbits -multisubset of -subset of composition of with terms orbits partition of into ≤ subsets partition of into ≤ elements partition of into subsets × orbits partition of into ≤ parts partition of into ≤ parts 1 partition of into parts
The particular notations used are: the falling factorial power , the rising factorial power , the factorial the Stirling number of the second kind , denoting the number of ways to partition a set of elements into non-empty subsets the binomial coefficient