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.Example:Example:Example:Example:Example:Example:No conditions x n {displaystyle x^{n}} ∑ i = 0 n { x i } {displaystyle sum _{i=0}^{n}left{{x atop i} ight}} Each gets at most one x n _ {displaystyle x^{underline {n}}} Each gets at least one x ! { n x } {displaystyle x!left{{n atop x} ight}} { n x } {displaystyle left{{n atop x} ight}} Each gets exactly onepermutationsordered functionsbroken permutations ( ≤ x {displaystyle leq x} parts)Each gets at least oneordered onto functionsbroken permutations (x parts)No conditions ( x + n − 1 n ) {displaystyle left({x+n-1 atop n} ight)} number partitions ( ≤ x {displaystyle leq x} parts)Each gets at most one ( x n ) {displaystyle left({x atop n} ight)} Each gets at least onecompositions (x parts) p x ( n ) {displaystyle p_{x}(n)} Each gets exactly one 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 n = | N | {displaystyle n=|N|} and x = | X | {displaystyle x=|X|} 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 f : N → X {displaystyle f:N o X} .