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.
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.
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.
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.
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 first two rows and columns of the table below correspond to sampling with and without replacement, with and without consideration of order.
Sampling without replacement where ordering does not matter is comparable to a single multivariate hypergeometric distribution.
[2] In all the injective cases (sampling without replacement), the number of sets of choices is zero unless N ≤ X.
("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.)
Then, we count how many choices we have made, and if it is not equal to N, throw out the entire set and repeat.
The labelling and selection points of view are not well compatible with permutation of the elements of X, 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 X may be freely permuted.
must be injective, then the selection must involve n distinct elements of X, so it is a subset of X of size n, also called an n-combination.
When in addition one identifies under permutations of N, this amounts to forgetting the groups themselves but retaining only their sizes.
How many ways can you place n plain balls into x marked boxes, with no other rules on placement?
How many ways can you place n plain balls into x marked boxes, with no multi-packs allowed?
How many ways can you place n marked balls into x plain boxes, with no other rules on placement?
How many ways can you place n marked balls into x plain boxes, with no multi-packs allowed?
The formula is Note that if n > x then one obtains a factor zero, so in this case there are no injective functions N → X at all; this is just a restatement of the pigeonhole principle.
This is also equivalent to counting the compositions of n with x (non-zero) terms, by listing the multiplicities of the elements of x 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 n by x, the result is Note that when n < x there are no surjective functions N → X 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 form of the result suggests looking for a manner to associate a class of surjective functions N → X directly to a subset of n − x elements chosen from a total of n − 1, which can be done as follows.
This argument is basically the one given at stars and bars, except that there the complementary choice of x − 1 "separations" is made.
The only fact that makes the result depend on n and x at all is that the existence of any such sequences to begin with requires n ≤ x, by the pigeonhole principle.
Its value can be described using a recursion relation or using generating functions, but unlike binomial coefficients there is no closed formula for these numbers that does not involve a summation.
As a consequence one is counting equivalence relations on N with at most x classes, and the result is obtained from the mentioned case by summation over values up to x, giving
, but the latter expression would give 0 for the case n = x = 0 (by the usual convention that binomial coefficients with a negative lower index are always 0).
Another generalization called the twentyfold way was developed by Kenneth P. Bogart in his book "Combinatorics Through Guided Discovery".