Twelvefold way
Encyclopedia
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, multiset
s, and partitions either of a set
or of a number
. The idea of the classification is due to Gian-Carlo Rota
, and the name was suggested by Joel Spencer
.
Let N and X be finite sets. Let n = |N| and x = |X|. Thus N is an n-set, and X is an x-set. The general problem we consider is the enumeration of functions
from N to X.
There are three different conditions
which may be imposed upon ƒ : N → X.
A possible fourth condition of being bijective
is not included, since the set of such functions will be empty unless n = x, 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 relation
s which may be defined on the set of functions
from N to X.
Formally, the last three cases mean that the problem is taken to be counting the orbits of the natural action of respectively the symmetric group
of N, the symmetric group of X, and of the product of the two groups, 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 modulo
permutations of N and/or of X is reflected by calling the balls respectively the boxes "indistinguishable". This is an imprecise formulation (in practice individual balls and boxes can always be distinguished by their location, and one could not assign different balls to different boxes without distinguishing them), 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 respectively of boxes; this is what the action by permutations of N and/or of X formalizes. In fact the case of indistinguishable boxes is somewhat harder to visualize than that of indistinguishable balls, since a configuration is inevitably presented with some ordering of the boxes; permuting the boxes will then appear as a permutation of their contents.
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 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. The labelling and selection points of view are more or less equivalent when N 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 n elements from X is made.
For an unordered selection the same kind of distinction applies. If ƒ 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
. Without the requirement, a same element of X may occur multiple times in the selection, and the result is a multiset
of size n of elements from X, also called an n-multicombination or n-combination with repetition.
In these cases the requirement of a surjective ƒ means that every label is to be used at least once, respectively that every element of X be included in the selection at least once. Such a requirement is less natural to handle mathematically, and indeed the former case is more easily viewed first as a grouping of elements of N, with in addition a labelling of the groups by the elements of X.
When in addition one identifies under permutations of N, 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 n. This gives the combinatorial notion of a partition
of the number n, into exactly x (for surjective ƒ) or at most x (for arbitrary ƒ) parts.
Formulas for the different cases of the twelvefold way are summarized in the table on the right; each table entry links to a subsection below explaining the formula. The particular notations used are the following:
Note that if n > x 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.
, which is therefore given by
s with n elements (also called n-multicombinations) of elements from X. The reason is that for each element of X it is determined how many elements of N are mapped to it by f, while two functions that give the same such "multiplicities" to each element of X can always be transformed into another by a permutation of N. The formula counting all functions is not useful here, because the number of them grouped together by permutations of N varies from one function to another. Rather, as explained under combinations, the number of n-multicombinations from a set with x elements can be seen to be the same as the number of n-combinations from a set with elements. This reduces the problem to another one in the twelvefold way, and gives as result
s with n elements of elements from X, for which each element of X occurs at least once. This is also equivalent to counting the compositions
of n with x (non-zero) parts, 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 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 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 N and X, and note that by applying a suitable permutation of N, every surjective function can be transformed into a unique weakly increasing (and of course still surjective) function. If one connects the elements of N in order by arcs into a linear graph, then choosing any subset of arcs and removing the rest, one obtains a graph with x connected components, and by sending these to the successive elements of X, one obtains a weakly increasing surjective function ; also the sizes of the connected components give a composition of n into x parts. This argument is basically the one given at stars and bars
, except that there the complementary choice of "separations" is made.
, using the Iverson bracket.
.
of N into x (non-empty) subsets, or counting equivalence relation
s on N with exactly x classes. Indeed for any surjective function , the relation of having the same image under f is such an equivalence relation, and it does not change when a permutation of X is subsequently applied; conversely one can turn such an equivalence relation into a surjective function by assigning the elements of X in some manner to the x equivalence classes. The number of such partitions or equivalence relations is by definition the Stirling number of the second kind S(n,x), also written
. Its value can be described using a recursion relation or using generating function
s, but unlike binomial coefficients there is no closed formula for these numbers that does not involve a summation
.
.
s of the number n into x non-zero parts. Compared to the case of counting surjective functions up to permutations of X only (
), one only retains the sizes of the equivalence classes that the function partitions N into (including the multiplicity of each size), since two equivalence relations can be transformed into one another by a permutation of N if and only if the sizes of their classes match. This is precisely what distinguishes the notion of partition of n from that of partition of N, so as a result one gets by definition the number px(n) of partitions of n into x non-zero parts.
. By adding a unit to each of the x parts one obtains a partition of into x nonzero parts, and this correspondence is bijective; hence the expression (but not its computation) can be simplified by writing it as 
.
In particular in the case of counting multisets with n elements taken from X, the given expression
is equivalent in most cases to 
, 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). Similarly, for the case of counting compositions of n with x non-zero parts, the given expression 
is almost equivalent to the expression 
given by the stars and bars
argument, but the latter gives incorrect values for n = 0 and all values of x. For the cases where the result involves a summation, namely those of counting partitions of N into at most x non-empty subsets or partitions of n into at most x non-zero parts, the summation index is taken to start at 0; although the corresponding term is zero whenever n > 0, it is the unique non-zero term when n = 0, and the result would be wrong for those cases if the summation were taken to start at 1.
of permutations to act on N and X. If G is a group of permutations of N, and H is a group of permutations of X, then we count equivalence classes of functions
. Two functions 
and 
are considered equivalent if, and only if, there exist 
so that 
. This extension leads to notions such as cyclic
and dihedral
permutations, as well as cyclic and dihedral partitions of numbers and sets.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
, 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
Counting
Counting is the action of finding the number of elements of a finite set of objects. The traditional way of counting consists of continually increasing a counter by a unit for every element of the set, in some order, while marking those elements to avoid visiting the same element more than once,...
permutations, combinations, multiset
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
s, and partitions either of a set
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
or of a number
Partition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
. The idea of the classification is due to Gian-Carlo Rota
Gian-Carlo Rota
Gian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...
, and the name was suggested by Joel Spencer
Joel Spencer
Joel Spencer is an American mathematician. He is a combinatorialist who has worked on probabilistic methods in combinatorics and on Ramsey theory. He received his doctorate from Harvard University in 1970, under the supervision of Andrew Gleason...
.
Let N and X be finite sets. Let n = |N| and x = |X|. Thus N is an n-set, and X is an x-set. The general problem we consider is the enumeration of functions
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
from N to X.
There are three different conditions
Material conditional
The material conditional, also known as material implication, is a binary truth function, such that the compound sentence p→q is logically equivalent to the negative compound: not . A material conditional compound itself is often simply called a conditional...
which may be imposed upon ƒ : N → X.
- No condition: Each ƒ : Na can produce any Xb, thus each Xb can occur multiple times.
- ƒ is injectiveInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
: Each ƒ : Na must produce a unique Xb, thus each Xb can only occur once. - ƒ is surjectiveSurjective functionIn mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...
: There must be at least one ƒ : Na → Xb for each Xb in X, thus each Xb will occur at least once.
A possible fourth condition of being bijective
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
is not included, since the set of such functions will be empty unless n = x, 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 relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
s which may be defined on the set of functions
from N to X.
- equality;
- equality up toUp toIn mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
a permutationPermutationIn mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of N; - equality up to a permutation of X;
- equality up to permutations of N and X.
Formally, the last three cases mean that the problem is taken to be counting the orbits of the natural action of respectively the symmetric group
Symmetric group
In mathematics, the symmetric group Sn on a finite set of n symbols is the group whose elements are all the permutations of the n symbols, and whose group operation is the composition of such permutations, which are treated as bijective functions from the set of symbols to itself...
of N, the symmetric group of X, and of the product of the two groups, 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., 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 compositionComposition (number theory)In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of positive integers. Two sequences that differ in the order of their terms define different compositions of their sum, while they are considered to define the same partition of that number. Any integer...
s of the number n into x parts is equivalent to counting all surjective functions N → X up to permutations of N. - Counting partitions of the number n into x parts is equivalent to counting all surjective functions N → X up to permutations of both N and X.
Interpretations
The various problems in the twelvefold way may be considered from different points of view.Balls and boxes
Traditionally many of the problems in twelvefold way have been formulated in terms of placing balls in boxes (or some similar visualization) instead of defining functions. The set N can be identified with a set of balls, and X with a set of boxes; then function ƒ : N → X then describes a way to distribute the balls into the boxes, namely by putting each ball b into box ƒ(b). Thus the property that a function ascribes a unique image to each value in its domain is reflected by the property that any ball can go into only one box (together with the requirement that no ball should remain outside of the boxes), whereas any box can accommodate (in principle) an arbitrary number of balls. Requiring in addition ƒ to be injective means forbidding to put more than one ball in any one box, while requiring ƒ to be surjective means insisting that every box contain at least one ball.Counting modulo
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
permutations of N and/or of X is reflected by calling the balls respectively the boxes "indistinguishable". This is an imprecise formulation (in practice individual balls and boxes can always be distinguished by their location, and one could not assign different balls to different boxes without distinguishing them), 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 respectively of boxes; this is what the action by permutations of N and/or of X formalizes. In fact the case of indistinguishable boxes is somewhat harder to visualize than that of indistinguishable balls, since a configuration is inevitably presented with some ordering of the boxes; permuting the boxes will then appear as a permutation of their contents.
Selection, labelling, grouping
A function ƒ : N → X can be considered from a the perspective of X or of N. This leads to different views:- the function ƒ labels each element of N by an element of X.
- the function ƒ selects (chooses) an element of the set X for each element of N, a total of n choices.
- the function ƒ groups the elements of N together that are mapped to the same element of X.
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 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. The labelling and selection points of view are more or less equivalent when N 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 n elements from X is made.
Labelling and selection with or without repetition
When viewing ƒ as a labelling of the elements of N, the latter may be thought of as arranged in a sequence, and the labels as being successively assigned to them. A requirement that ƒ be injective means that no label can be used a second time; the result is a sequence of labels without repetition. In the absence of such a requirement, the terminology "sequences with repetition" is used, meaning that labels may be used more than once (although sequences that happen to be without repetition are also allowed).For an unordered selection the same kind of distinction applies. If ƒ 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
Combination
In mathematics a combination is a way of selecting several things out of a larger group, where order does not matter. In smaller cases it is possible to count the number of combinations...
. Without the requirement, a same element of X may occur multiple times in the selection, and the result is a multiset
Multiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
of size n of elements from X, also called an n-multicombination or n-combination with repetition.
In these cases the requirement of a surjective ƒ means that every label is to be used at least once, respectively that every element of X be included in the selection at least once. Such a requirement is less natural to handle mathematically, and indeed the former case is more easily viewed first as a grouping of elements of N, with in addition a labelling of the groups by the elements of X.
Partitions of sets and numbers
When viewing ƒ as a grouping of the elements of N (which assumes one identifies under permutations of X), requiring ƒ to be surjective means the number of groups must be exactly x. Without this requirement the number of groups can be at most x. The requirement of injective ƒ means each element of N must be a group in itself, which leaves at most one valid grouping and therefore gives a rather uninteresting counting problem.When in addition one identifies under permutations of N, 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 n. This gives the combinatorial notion of a partition
Partition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
of the number n, into exactly x (for surjective ƒ) or at most x (for arbitrary ƒ) parts.
Formulas
| Any f | Injective f | Surjective f | |
|---|---|---|---|
| Distinct |  |
 |
 |
| Sn orbits |  |
 |
 |
| Sx orbits |  |
 |
 |
| Sn×Sx orbits |  |
 |
 |
Formulas for the different cases of the twelvefold way are summarized in the table on the right; each table entry links to a subsection below explaining the formula. The particular notations used are the following:
- the falling factorial power
, - the factorialFactorialIn mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...
- the Stirling number of the second kind
, denoting the number of ways to partitionPartition of a setIn mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
a set of n elements into k subsets - the binomial coefficientBinomial coefficientIn mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
- the Iverson bracket encoding a truth value as 0 or 1
- the number
of partitionPartition (number theory)In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
s of n into k parts
Details of the different cases
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.Functions from N to X
This case is equivalent to counting sequences of n elements of X with no restriction: a function is determined by the n images of the elements of N, which can each be independently chosen among the elements of x. This gives a total of xn possibilities.Example:
Injective functions from N to X
This case is equivalent to counting sequences of n distinct elements of X, also called n-permutations of X, or sequences without repetitions; again this sequence is formed by the n images of the elements of N. This case differs from the one of unrestricted sequences in that there is one choice less for the second element, two less for the third element, and so on. Therefore instead of by an ordinary power of x, the value is given by a falling factorial power of x, in which each successive factor is one less than the previous one. The formula is
Note that if n > x 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:
Injective functions from N to X, up to a permutation of N
This case is equivalent to counting subsets of n elements of X, also called n-combinations of X: among the sequences of n distinct elements of X, those that differ only in the order of their terms are identified by permutations of N. Since in all cases this groups together exactly n! different sequences, we can divide the number of such sequences by n! to get the number of n-combinations of X. This number is known as the binomial coefficientBinomial coefficient
In mathematics, binomial coefficients are a family of positive integers that occur as coefficients in the binomial theorem. They are indexed by two nonnegative integers; the binomial coefficient indexed by n and k is usually written \tbinom nk , and it is the coefficient of the x k term in...
, which is therefore given byFunctions from N to X, up to a permutation of N
This case is equivalent to counting multisetMultiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
s with n elements (also called n-multicombinations) of elements from X. The reason is that for each element of X it is determined how many elements of N are mapped to it by f, while two functions that give the same such "multiplicities" to each element of X can always be transformed into another by a permutation of N. The formula counting all functions is not useful here, because the number of them grouped together by permutations of N varies from one function to another. Rather, as explained under combinations, the number of n-multicombinations from a set with x elements can be seen to be the same as the number of n-combinations from a set with elements. This reduces the problem to another one in the twelvefold way, and gives as result
Surjective functions from N to X, up to a permutation of N
This case is equivalent to counting a multisetMultiset
In mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
s with n elements of elements from X, for which each element of X occurs at least once. This is also equivalent to counting the compositions
Composition (number theory)
In mathematics, a composition of an integer n is a way of writing n as the sum of a sequence of positive integers. Two sequences that differ in the order of their terms define different compositions of their sum, while they are considered to define the same partition of that number. Any integer...
of n with x (non-zero) parts, 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 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 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 N and X, and note that by applying a suitable permutation of N, every surjective function can be transformed into a unique weakly increasing (and of course still surjective) function. If one connects the elements of N in order by arcs into a linear graph, then choosing any subset of arcs and removing the rest, one obtains a graph with x connected components, and by sending these to the successive elements of X, one obtains a weakly increasing surjective function ; also the sizes of the connected components give a composition of n into x parts. This argument is basically the one given at stars and bars
Stars and bars (probability)
In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his classic book on probability.- Theorem one :...
, except that there the complementary choice of "separations" is made.
Injective functions from N to X, up to a permutation of X
In this case we consider sequences of n distinct elements from X, but identify those obtained from one another by applying to each element a permutation of X. It is easy to see that two different such sequences can always be identified: the permutation must map term i of the first sequence to term i 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 n and x at all is that the existence of any such sequences to begin with requires n ≤ x, by the pigeonhole principle. The number is therefore expressed as, using the Iverson bracket.Injective functions from N to X, up to permutations of N and X
This case is reduced to the previous one: since all sequences of n distinct elements from X can already be transformed into each other by applying a permutation of X to each of their terms, also allowing reordering of the terms does not give any new identifications; the number remains.Surjective functions from N to X, up to a permutation of X
This case is equivalent to counting partitionsPartition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...
of N into x (non-empty) subsets, or counting equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
s on N with exactly x classes. Indeed for any surjective function , the relation of having the same image under f is such an equivalence relation, and it does not change when a permutation of X is subsequently applied; conversely one can turn such an equivalence relation into a surjective function by assigning the elements of X in some manner to the x equivalence classes. The number of such partitions or equivalence relations is by definition the Stirling number of the second kind S(n,x), also written
. Its value can be described using a recursion relation or using generating functionGenerating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...
s, but unlike binomial coefficients there is no closed formula for these numbers that does not involve a summation
Summation
Summation is the operation of adding a sequence of numbers; the result is their sum or total. If numbers are added sequentially from left to right, any intermediate result is a partial sum, prefix sum, or running total of the summation. The numbers to be summed may be integers, rational numbers,...
.
Surjective functions from N to X
For each surjective function , its orbit under permutations of X has x! elements, since composition (on the left) with two distinct permutations of X never gives the same function on N (the permutations must differ at some element of X, which can always be written as f(i) for some i ∈ N, and the compositions will then differ at i). It follows that the number for this case is x! times the number for the previous case, that isExample:
Functions from N to X, up to a permutation of X
This case is like the corresponding one for surjective functions, but some elements of x might not correspond to any equivalence class at all (since one considers functions up to a permutation of X, it does not matter which elements are concerned, just how many). 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.Surjective functions from N to X, up to permutations of N and X
This case is equivalent to counting partitionPartition (number theory)
In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a...
s of the number n into x non-zero parts. Compared to the case of counting surjective functions up to permutations of X only (
), one only retains the sizes of the equivalence classes that the function partitions N into (including the multiplicity of each size), since two equivalence relations can be transformed into one another by a permutation of N if and only if the sizes of their classes match. This is precisely what distinguishes the notion of partition of n from that of partition of N, so as a result one gets by definition the number px(n) of partitions of n into x non-zero parts.Functions from N to X, up to permutations of N and X
This case is equivalent to counting partitions of the number n into x parts with parts 0 allowed. The association is the same as for the previous case, adding for each element of X not in the image of the function one can associate a part 0 to the partition. Each partition of n into at most x non-zero parts can be extended to such a partition by adding the required number of zeroes, and this accounts for all possibilities, so the result is. By adding a unit to each of the x parts one obtains a partition of into x nonzero parts, and this correspondence is bijective; hence the expression (but not its computation) can be simplified by writing it as .Extremal cases
The above formulas give the proper values for all finite sets N and X. 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 N or X are empty. The following considerations apply to such cases.- For every set X there is exactly one function from the empty set to X (there are no values of this function to specify), which is always injective, but never surjective unless X is (also) empty.
- For every non-empty set N there are no functions from N to the empty set (there is at least one value of the function that must be specified, but it cannot).
- When n > x there are no injective functions , and if n < x there are no surjective functions .
- The expressions used in the formulas have as particular values
-
- (the first three are instances of an empty productEmpty productIn mathematics, an empty product, or nullary product, is the result of multiplying no factors. It is equal to the multiplicative identity 1, given that it exists for the multiplication operation in question, just as the empty sum—the result of adding no numbers—is zero, or the additive...
, and the value
is given by the conventional extension of binomial coefficients to arbitrary values of the upper index), while
In particular in the case of counting multisets with n elements taken from X, the given expression
is equivalent in most cases to , 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). Similarly, for the case of counting compositions of n with x non-zero parts, the given expression is almost equivalent to the expression given by the stars and barsStars and bars (probability)
In the context of combinatorial mathematics, stars and bars is a graphical aid for deriving certain combinatorial theorems. It was popularized by William Feller in his classic book on probability.- Theorem one :...
argument, but the latter gives incorrect values for n = 0 and all values of x. For the cases where the result involves a summation, namely those of counting partitions of N into at most x non-empty subsets or partitions of n into at most x non-zero parts, the summation index is taken to start at 0; although the corresponding term is zero whenever n > 0, it is the unique non-zero term when n = 0, and the result would be wrong for those cases if the summation were taken to start at 1.
Generalizations
We can generalize further by allowing other groupsGroup (mathematics)
In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
of permutations to act on N and X. If G is a group of permutations of N, and H is a group of permutations of X, then we count equivalence classes of functions
. Two functions and are considered equivalent if, and only if, there exist so that . This extension leads to notions such as cyclicCyclic permutation
A cyclic permutation or circular permutation is a permutation built from one or more sets of elements in cyclic order.The notion "cyclic permutation" is used in different, but related ways:- Definition 1 :right|mapping of permutation...
and dihedral
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
permutations, as well as cyclic and dihedral partitions of numbers and sets.