Twelvefold way

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. Let N and X be finite sets. Let and be the cardinality of the sets. Thus N is an n-set, and X is an x-set. 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 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 for a in N must be distinct from every other, and so each b in X may occur at most once in the of f. f is surjective: for each b in X there must be at least one a in N such that , thus each b will occur at least once in the image of f. (The condition "f is bijective" is only an option when ; 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.