Twelvefold Way

In combinatorics, the twelvefold way is a name given to 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.

Let and be finite sets. Let and be the cardinality of the sets. Thus is an -set, and is an -set. The general problem we consider is the enumeration of functions from to, subject to one of the three following restrictions:

1. No condition: each in may be sent by to any in, and each may occur multiple times.
2. 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 .
3. 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 .

A possible fourth condition of being bijective is not included, since the set of such functions will be empty unless, in which case the condition is equivalent both to being injective and to being surjective; therefore considering this condition would not add any interesting problems.

There are four different equivalence relations which may be defined on the set of functions from to .

1. equality;
2. equality up to a permutation of ;
3. equality up to a permutation of ;
4. equality up to permutations of and .

Formally, the last three cases mean that the problem is taken to be counting the orbits of the natural action of the symmetric group of N, the symmetric group of X, and of the product of the two groups, respectively, on the appropriate sets of functions. These criteria can be paired in 3 × 4 = 12 ways.

These 12 types of problems do not involve the same difficulties, and there is not one systematic method for solving them. Indeed two of the problems are trivial (since all injective functions N → X, if any, are equivalent under permutations of X), some problems allow a solution expressed by a multiplicative formula in terms of n and x, while for the remaining problems the solution can only be expressed in terms of combinatorial functions adapted to the problem, notably Stirling numbers and functions counting partitions of numbers with 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.

The various problems in the twelvefold way may be considered from different points of view.