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, and the name was suggested by Joel Spencer.[1]
Let and be finite sets. Let
n=|N|
x=|X|
f:N\toX
The functions are subject to one of the three following restrictions:
f(a)
f(a)=b
n=x
There are four different equivalence relations which may be defined on the set of functions from to :
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.
The various problems in the twelvefold way may be considered from different points of view.
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
f:N\toX
f(a)
f
f
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.
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
f
f
From the perspective of sampling, the column labeled "Surjective
f
A function
f:N\toX
f
f
f
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.
When viewing
f
f
When viewing
f
f
The requirement that
f
When viewing
f
f
f
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
f
f
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.
f | Any f | Injective f | Surjective f | |
|---|---|---|---|---|
| any function : → | injective function : → | surjective function : → | ||
| Distinct | -sequence in xn | -permutation of x\underline | composition of with subsets x!\left\{{n\atopx}\right\} | |
| orbits | -subset of \binom{x}{n} | composition of with terms \binom{n-1}{n-x} | ||
| orbits | partition of into ≤ elements [n\leqx] | partition of into subsets \left\{{n\atopx}\right\} | ||
| × orbits | partition of into ≤ parts px(n+x) | partition of into ≤ parts 1 [n\leqx] | partition of into parts px(n) |
The particular notations used are:
This is a quick summary of what the different cases mean. The cases are described in detail below.
Think of a set of numbered items (numbered from 1 to), from which we choose, yielding an ordered list of the items: e.g. if there are
x=10
n=3
Then the columns mean:
n\leqx
n\geqx
And the rows mean:
The chart below is similar to the chart above, but instead of showing the formulas, it gives an intuitive understanding of their meaning using the familiar balls and boxes example. The rows represent the distinctness of the balls and boxes. The columns represent if multi-packs (more than one ball in one box), or empty boxes are allowed. The cells in the chart show the question that is answered by solving the formula given in the formula chart above.
| Any (no rules on placement) | Injective (no multi-packs allowed) | Surjective (no empty boxes allowed) | ||
|---|---|---|---|---|
| -sequence in How many ways can you place marked balls into marked boxes, with no other rules on placement? | -permutation in How many ways can you place marked balls into marked boxes, with no multi-packs allowed? | composition of with subsets How many ways can you place marked balls into marked boxes, with no empty boxes allowed? | ||
| -subset of How many ways can you place plain balls into marked boxes, with no multi-packs allowed? | composition of with termsHow many ways can you place plain balls into marked boxes, with no empty boxes allowed? | |||
| partition of into ≤ partsHow many ways can you place plain balls into plain boxes, with no other rules on placement? | partition of into ≤ parts 1How many ways can you place plain balls into plain boxes, with no multi-packs allowed? | partition of into partsHow many ways can you place plain balls into plain boxes, with no empty boxes allowed? |
The cases below are ordered in such a way as to group those cases for which the arguments used in counting are related, which is not the ordering in the table given.
This case is equivalent to counting sequences of elements of with no restriction: a function is determined by the images of the elements of, which can each be independently chosen among the elements of . This gives a total of possibilities.
Example:X=\{a,b,c\},N=\{1,2\},then
\left\vert\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}\right\vert=32=9
This case is equivalent to counting sequences of distinct elements of, also called -permutations of, or sequences without repetitions; again this sequence is formed by the images of the elements of . This case differs from the one of unrestricted sequences in that there is one choice fewer for the second element, two fewer for the third element, and so on. Therefore instead of by an ordinary power of, the value is given by a falling factorial power of, in which each successive factor is one fewer than the previous one. The formula is
x\underline=x(x-1) … (x-n+1).
Note that if then one obtains a factor zero, so in this case there are no injective functions at all; this is just a restatement of the pigeonhole principle.
Example:X=\{a,b,c,d\},N=\{1,2\},then
\left\vert\{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert=4\underline2=4 x 3=12
\tbinomxn
\binomxn=
| x\underline | |
| n! |
=
| x(x-1) … (x-n+2)(x-n+1) | |
| n(n-1) … 2 ⋅ 1 |
.
Example:X=\{a,b,c,d\},N=\{1,2\},then
\left\vert\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}\right\vert=
4\underline2 2! =
4 x 3 2 =6
This case is equivalent to counting multisets with elements from (also called -multicombinations). The reason is that for each element of it is determined how many elements of are mapped to it by, while two functions that give the same such "multiplicities" to each element of can always be transformed into another by a permutation of . The formula counting all functions is not useful here, because the number of them grouped together by permutations of varies from one function to another. Rather, as explained under combinations, the number of -multicombinations from a set with elements can be seen to be the same as the number of -combinations from a set with elements. This reduces the problem to another one in the twelvefold way, and gives as result
\binom{x+n-1}n=
| (x+n-1)(x+n-2) … (x+1)x | |
| n(n-1) … 2 ⋅ 1 |
=
| x\overline | |
| n! |
.
Example:X=\{a,b,c\},N=\{1,2\},then
\left\vert\{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}\right\vert=
3\overline 2! =
4 x 3 2 =6
This case is equivalent to counting multisets with elements from, for which each element of occurs at least once. This is also equivalent to counting the compositions of with (non-zero) terms, by listing the multiplicities of the elements of in order. The correspondence between functions and multisets is the same as in the previous case, and the surjectivity requirement means that all multiplicities are at least one. By decreasing all multiplicities by 1, this reduces to the previous case; since the change decreases the value of by, the result is
\binom{n-1}{n-x}.
Note that when < there are no surjective functions at all (a kind of "empty pigeonhole" principle); this is taken into account in the formula, by the convention that binomial coefficients are always 0 if the lower index is negative. The same value is also given by the expression
\binom{n-1}{x-1},
except in the extreme case, where with the former expression correctly gives
\tbinom{-1}0=1
\tbinom{-1}{-1}=0
The form of the result suggests looking for a manner to associate a class of surjective functions directly to a subset of elements chosen from a total of, which can be done as follows. First choose a total ordering of the sets and, and note that by applying a suitable permutation of, every surjective function can be transformed into a unique weakly increasing (and of course still surjective) function. If one connects the elements of in order by arcs into a linear graph, then choosing any subset of arcs and removing the rest, one obtains a graph with connected components, and by sending these to the successive elements of, one obtains a weakly increasing surjective function ; also the sizes of the connected components give a composition of into parts. This argument is basically the one given at stars and bars, except that there the complementary choice of "separations" is made.
Example:X=\{a,b\},N=\{1,2,3\},then
\left\vert\{\{a,a,b\},\{a,b,b\}\}\right\vert=\binom{3-1}{3-2}=\binom{2}{1}=
2! 1! x (2-1)! =2
In this case we consider sequences of distinct elements from, but identify those obtained from one another by applying to each element a permutation of . It is easy to see that two different such sequences can always be identified: the permutation must map term of the first sequence to term of the second sequence, and since no value occurs twice in either sequence these requirements do not contradict each other; it remains to map the elements not occurring in the first sequence bijectively to those not occurring in the second sequence in an arbitrary way. The only fact that makes the result depend on and at all is that the existence of any such sequences to begin with requires, by the pigeonhole principle. The number is therefore expressed as
[n\leqx]
This case is reduced to the previous one: since all sequences of distinct elements from can already be transformed into each other by applying a permutation of to each of their terms, also allowing reordering of the terms does not give any new identifications; the number remains
[n\leqx]
This case is equivalent to counting partitions of into (non-empty) subsets, or counting equivalence relations on with exactly classes. Indeed, for any surjective function, the relation of having the same image under is such an equivalence relation, and it does not change when a permutation of is subsequently applied; conversely one can turn such an equivalence relation into a surjective function by assigning the elements of in some manner to the equivalence classes. The number of such partitions or equivalence relations is by definition the Stirling number of the second kind, also written
style\{{n\atopx}\}
For each surjective function, its orbit under permutations of has ! elements, since composition (on the left) with two distinct permutations of never gives the same function on (the permutations must differ at some element of, which can always be written as
f(i)
stylex!\{{n\atopx}\}.
Example:X=\{a,b\},N=\{1,2,3\},then
\left\vert\{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}\right\vert=2!\left\{{3\atop2}\right\}=2 x 3=6
This case is like the corresponding one for surjective functions, but some elements of might not correspond to any equivalence class at all (since one considers functions up to a permutation of, it does not matter which elements are concerned, just how many). As a consequence one is counting equivalence relations on with at most classes, and the result is obtained from the mentioned case by summation over values up to, giving
| x | |
| style\sum | |
| k=0 |
\{{n\atopk}\}
| n | |
| style\sum | |
| k=0 |
\{{n\atopk}\}
This case is equivalent to counting partitions of the number into non-zero parts. Compared to the case of counting surjective functions up to permutations of only (
style\{{n\atopx}\}
This case is equivalent to counting partitions of the number into ≤ parts. The association is the same as for the previous case, except that now some parts of the partition may be equal to 0. (Specifically, they correspond to elements of not in the image of the function.) Each partition of into at most non-zero parts can be extended to such a partition by adding the required number of zeroes, and this accounts for all possibilities exactly once, so the result is given by
| x | |
| style\sum | |
| k=0 |
pk(n)
px(n+x)
The above formulas give the proper values for all finite sets and . In some cases there are alternative formulas which are almost equivalent, but which do not give the correct result in some extremal cases, such as when or are empty. The following considerations apply to such cases.
00=0\underline=0!=\binom00=\binom{-1}0=\left\{{0\atop0}\right\}=p0(0)=1
(the first three are instances of an empty product, and the value
\tbinom{-1}{0}=\tfrac{(-1)\underline{0
\left\{{n\atopx}\right\}=px(n)=0 \hbox{whenevereither}n>0=x\hbox{or}0\leqn<x.
In particular in the case of counting multisets with elements taken from, the given expression
\tbinom{n+x-1}n
\tbinom{n+x-1}{x-1}
\tbinom{n-1}{n-x}
\tbinom{n-1}{x-1}
We can generalize further by allowing other groups of permutations to act on and . If is a group of permutations of, and is a group of permutations of, then we count equivalence classes of functions
f\colonN → X
g\inG,h\inH
F=h\circf\circg
Another generalization called the twentyfold way was developed by Kenneth P. Bogart in his book "Combinatorics Through Guided Discovery". In the problem of distributing objects to boxes both the objects and the boxes may be identical or distinct. Bogart identifies 20 cases.[3] Robert A. Proctor has constructed the thirtyfold way.[4]
| Objects | Condition of distribution | Recipients | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Distinct | Identical | ||||||||||||
| 1 | rowspan="4" | Distinct | No restriction | -sequence in xn | partition of into ≤ subsets
\atopi}\right\} | ||||||||
| 2 | At most one each | -permutation of x\underline | \begin{cases}1&ifn\leqx\ 0&otherwise\end{cases} | ||||||||||
| 3 | At least one each | composition of with subsets x!\left\{{n\atopx}\right\} | partition of into subsets \left\{{n\atopx}\right\} | ||||||||||
| 4 | Exactly one each | n!=x! permutations | \begin{cases}1&ifn=x\ 0&otherwise\end{cases} | ||||||||||
| 5 | rowspan="2" | Distinct, ordered | No restriction | (n+x-1)\underline ordered functions |
L(n,i) broken permutations ( \leqx Where L(n,i) | ||||||||
| 6 | At least one each | (n)\underline ordered onto functions | L(n,x)=\left({n\atopx}\right)(n-1)\underline{n-x broken permutations (parts) Where L(n,x) | ||||||||||
| 7 | rowspan="4" | Identical | No restriction | -multisubset of \left({x+n-1\atopn}\right) |
pi(n) number partitions ( \leqx | ||||||||
| 8 | At most one each | -subset of \left({x\atopn}\right) | \begin{cases}1&ifn\leqx\ 0&otherwise\end{cases} | ||||||||||
| 9 | At least one each | \left({n-1\atopx-1}\right) compositions (parts) | partition of into parts px(n) | ||||||||||
| 10 | Exactly one each | \begin{cases}1&ifn=x\ 0&otherwise\end{cases} | \begin{cases}1&ifn=x\ 0&otherwise\end{cases} | ||||||||||