Twelvefold way

Template:Short description Template:Technical 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.

Overview

Let Template:Mvar and Template:Mvar be finite sets. Let $n=|N|$ and $x=|X|$ be the cardinalities of the sets. Thus Template:Mvar is a set with Template:Mvar elements, and Template:Mvar is a set with Template:Mvar elements.

The general problem we consider is the enumeration of equivalence classes of functions $f:N\to X$.

The functions are subject to one of the three following restrictions:

• No condition: each Template:Mvar in Template:Mvar may be sent by Template:Mvar to any Template:Mvar in Template:Mvar, and each Template:Mvar may occur multiple times.
• Template:Mvar is injective: each value $f(a)$ for Template:Mvar in Template:Mvar must be distinct from every other, and so each Template:Mvar in Template:Mvar may occur at most once in the image of Template:Mvar.
• Template:Mvar is surjective: for each Template:Mvar in Template:Mvar there must be at least one Template:Mvar in Template:Mvar such that $f(a)=b$, thus each Template:Mvar will occur at least once in the image of Template:Mvar.

(The condition "Template:Mvar is bijective" is only an option when $n=x$; but then it is equivalent to both "Template:Mvar is injective" and "Template:Mvar is surjective".)

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

• equality;
• equality up to a permutation of Template:Mvar;
• equality up to a permutation of Template:Mvar;
• equality up to permutations of Template:Mvar and Template:Mvar.

The three conditions on the functions and the four equivalence relations can be paired in Template:Math 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 Template:Mvar and Template:Mvar, 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 Template:Mvar-permutations (i.e., partial permutations or sequences without repetition) of Template:Mvar is equivalent to counting [[#case i|injective functions Template:Math]].
• Counting Template:Mvar-combinations of Template:Mvar is equivalent to counting [[#case in|injective functions Template:Math up to permutations of Template:Mvar]].
• Counting permutations of the set Template:Mvar is equivalent to counting injective functions Template:Math when Template:Mvar = Template:Mvar, and also to counting [[#case s|surjective functions Template:Math]] when Template:Math.
• Counting multisets of size Template:Mvar (also known as Template:Mvar-combinations with repetitions) of elements in Template:Mvar is equivalent to counting all [[#case fn|functions Template:Math up to permutations of Template:Mvar]].
• Counting partitions of the set Template:Mvar into Template:Mvar subsets is equivalent to counting all [[#case sx|surjective functions Template:Math up to permutations of Template:Mvar]].
• Counting compositions of the number Template:Mvar into Template:Mvar parts is equivalent to counting all [[#case sn|surjective functions Template:Math up to permutations of Template:Mvar]].

Viewpoints

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

Balls and boxes

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. The set Template:Mvar can be identified with a set of balls, and Template:Mvar with a set of boxes; the function $f:N\to X$ then describes a way to distribute the balls into the boxes, namely by putting each ball Template:Mvar into box $f(a)$. A function ascribes a unique image to each value in its domain; this property 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 an arbitrary number of balls. Requiring in addition $f$ to be injective means to forbid putting more than one ball in any one box, while requiring $f$ to be surjective means insisting that every box contain at least one ball.

Counting modulo permutations of Template:Mvar or Template:Mvar 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. This possibility of transformation is formalized by the action by permutations.

Sampling

Another way to think of some of the cases is in terms of sampling, in statistics. Imagine a population of Template:Mvar items (or people), of which we choose Template:Mvar. Two different schemes are normally described, known as "sampling with replacement" and "sampling without replacement". 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 result is that each choice is independent of all the other choices, and the set of samples is technically referred to as independent identically distributed. In the latter case, however, once we have chosen an item, we put it aside so that we can not choose it again. This means that the act of choosing an item has an effect on all the following choices (the particular item can not be seen again), so our choices are dependent on one another.

A second distinction among sampling schemes is whether ordering matters. For example, if we have ten items, of which we choose two, then the choice (4, 7) is different from (7, 4) if ordering matters; on the other hand, if ordering does not matter, then the choices (4, 7) and (7, 4) are equivalent.

The first two rows and columns of the table below correspond to sampling with and without replacement, with and without consideration of order. The cases of sampling with replacement are found in the column labeled "Any $f$", while the cases of sampling without replacement are found in the column labeled "Injective $f$". The cases where ordering matters are found in the row labeled "Distinct," and the cases where ordering does not matter are found in the row labeled "Template:Mvar_{Template:Mvar} orbits". Each table entry indicates how many different sets of choices there are, in a particular sampling scheme. Three of these table entries also correspond to probability distributions. Sampling with replacement where ordering matters is comparable to describing the joint distribution of Template:Mvar separate random variables, each with an Template:Mvar-fold categorical distribution. Sampling with replacement where ordering does not matter, however, is comparable to describing a single multinomial distribution of Template:Mvar draws from an Template:Mvar-fold category, where only the number seen of each category matters. Sampling without replacement where ordering does not matter is comparable to a single multivariate hypergeometric distribution. Sampling without replacement where order does matter does not seem to correspond to a probability distribution. In all the injective cases (sampling without replacement), the number of sets of choices is zero unless Template:Math. ("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.)

From the perspective of sampling, the column labeled "Surjective $f$" is somewhat strange: Essentially, we keep sampling with replacement until we have chosen each item at least once. Then, we count how many choices we have made, and if it is not equal to Template:Mvar, throw out the entire set and repeat. This is vaguely comparable to the coupon collector's problem, where the process involves "collecting" (by sampling with replacement) a set of Template:Mvar coupons until each coupon has been seen at least once. In all surjective cases, the number of sets of choices is zero unless Template:Math.

Labelling, selection, grouping

A function $f:N\to X$ can be considered from the perspective of Template:Mvar or of Template:Mvar. This leads to different views:

• the function $f$ labels each element of Template:Mvar by an element of Template:Mvar.
• the function $f$ selects (chooses) an element of the set Template:Mvar for each element of Template:Mvar, a total of Template:Mvar choices.
• the function $f$ groups the elements of Template:Mvar together that are mapped to the same element of Template:Mvar.

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 Template:Mvar, 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 Template:Mvar may be freely permuted. The labelling and selection points of view are more or less equivalent when Template:Mvar 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 Template:Mvar elements from Template:Mvar is made.

Labelling and selection with or without repetition

When viewing $f$ as a labelling of the elements of Template:Mvar, the latter may be thought of as arranged in a sequence, and the labels from Template:Mvar as being successively assigned to them. A requirement that $f$ 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).

When viewing $f$ as an unordered selection of the elements of Template:Mvar, the same kind of distinction applies. If $f$ must be injective, then the selection must involve Template:Mvar distinct elements of Template:Mvar, so it is a subset of Template:Mvar of size Template:Mvar, also called an Template:Mvar-combination. Without the requirement, one and the same element of Template:Mvar may occur multiple times in the selection, and the result is a multiset of size Template:Mvar of elements from Template:Mvar, also called an Template:Mvar-multicombination or Template:Mvar-combination with repetition.

The requirement that $f$ be surjective, from the viewpoint of labelling elements of Template:Mvar, means that every label is to be used at least once; from the viewpoint of selection from Template:Mvar, it means that every element of Template:Mvar must be included in the selection at least once. Labelling with surjection is equivalent to a grouping of elements of Template:Mvar followed by labeling each group by an element of Template:Mvar, and is accordingly somewhat more complicated to describe mathematically.

Partitions of sets and numbers

When viewing $f$ as a grouping of the elements of Template:Mvar (which assumes one identifies under permutations of Template:Mvar), requiring $f$ to be surjective means the number of groups must be exactly Template:Mvar. Without this requirement the number of groups can be at most Template:Mvar. The requirement of injective $f$ means each element of Template:Mvar 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 Template:Mvar, 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 Template:Mvar. This gives the combinatorial notion of a partition of the number Template:Mvar, into exactly Template:Mvar (for surjective $f$) or at most Template:Mvar (for arbitrary $f$) parts.

Formulas

Formulas for the different cases of the twelvefold way are summarized in the following table; each table entry links to a subsection below explaining the formula.

The twelve combinatorial objects and their enumeration formulas

$f$-class	Any $f$	Injective $f$	Surjective $f$
Distinct Template:Mvar	[[#case f|Template:Mvar-sequence in Template:Mvar $x^n$]]	[[#case i|Template:Mvar-permutation of Template:Mvar $x^{\underset{\_}{n}}$]]	[[#case s|composition of Template:Mvar with Template:Mvar subsets $x!\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$]]
Template:MvarTemplate:Mvar orbits Template:Math	[[#case fn|Template:Mvar-multisubset of Template:Mvar $(\genfrac{}{}{0ex}{}{x+n-1}{n})$]]	[[#case in|Template:Mvar-subset of Template:Mvar $(\genfrac{}{}{0ex}{}{x}{n})$]]	[[#case sn|composition of Template:Mvar with Template:Mvar terms $(\genfrac{}{}{0ex}{}{n-1}{n-x})$]]
Template:MvarTemplate:Mvar orbits Template:Math	[[#case fx|partition of Template:Mvar into ≤ Template:Mvar subsets $\sum _{k=0}^x\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$]]	[[#case ix|partition of Template:Mvar into ≤ Template:Mvar elements $[n\le x]$]]	[[#case sx|partition of Template:Mvar into Template:Mvar subsets $\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$]]
Template:MvarTemplate:Mvar×Template:MvarTemplate:Mvar orbits Template:Math	[[#case fnx|partition of Template:Mvar into ≤ Template:Mvar parts $p_x(n+x)$]]	[[#case inx|partition of Template:Mvar into ≤ Template:Mvar parts 1 $[n\le x]$]]	[[#case snx|partition of Template:Mvar into Template:Mvar parts $p_x(n)$]]

The particular notations used are:

• the falling factorial power $x^{\underset{\_}{n}}=\frac{x!}{(x-n)!}=x(x-1)(x-2)\cdots (x-n+1)$,
• the rising factorial power $x^{\bar{n}}=\frac{(x+n-1)!}{(x-1)!}=x(x+1)(x+2)\cdots (x+n-1)$,
• the factorial $n!=n^{\underset{\_}{n}}=n(n-1)(n-2)\cdots 1$
• the Stirling number of the second kind $\left\{\genfrac{}{}{0ex}{}{n}{k}\right\}$, denoting the number of ways to partition a set of Template:Mvar elements into Template:Mvar non-empty subsets
• the binomial coefficient $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_}{k}}}{k!}$
• the Iverson bracket [ ] encoding a truth value as 0 or 1
• the number $p_k(n)$ of partitions of Template:Mvar into Template:Mvar parts

Intuitive meaning of the rows and columns

This is a quick summary of what the different cases mean. The cases are described in detail below.

Think of a set of Template:Mvar numbered items (numbered from 1 to Template:Mvar), from which we choose Template:Mvar, yielding an ordered list of the items: e.g. if there are $x=10$ items of which we choose $n=3$, the result might be the list (5, 2, 10). We then count how many different such lists exist, sometimes first transforming the lists in ways that reduce the number of distinct possibilities.

Then the columns mean:

Any Template:Mvar

After we choose an item, we put it back, so we might choose it again.

Injective Template:Mvar

After we choose an item, we set it aside, so we can't choose it again; hence we'll end up with Template:Mvar distinct items. Necessarily, then, unless $n\le x$, no lists can be chosen at all.

Surjective Template:Mvar

After we choose an item, we put it back, so we might choose it again — but at the end, we have to end up having chosen each item at least once. Necessarily, then, unless $n\ge x$, no lists can be chosen at all.

And the rows mean:

Distinct

Leave the lists alone; count them directly.

Template:Mvar_{Template:Mvar} orbits

Before counting, sort the lists by the item number of the items chosen, so that order doesn't matter, e.g., (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10).

Template:Mvar_{Template:Mvar} orbits

Before counting, renumber the items seen so that the first item seen has number 1, the second 2, etc. Numbers may repeat if an item was seen more than once, e.g., (3, 5, 3), (5, 2, 5), (4, 9, 4) → (1, 2, 1) while (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2).

Template:Mvar_{Template:Mvar} × Template:Mvar_{Template:Mvar} orbits

Two lists count as the same if it is possible to both reorder and relabel them as above and produce the same result. For example, (3, 5, 3) and (2, 9, 9) count as the same because they can be reordered as (3, 3, 5) and (9, 9, 2) and then relabeling both produces the same list (1, 1, 2).

Intuitive meaning of the chart using balls and boxes scenario

The chart below is similar to the chart above, but instead of showing the formulas, it gives an intuitive understanding of their meaning using the familiar balls and boxes example. The rows represent the distinctness of the balls and boxes. The columns represent if multi-packs (more than one ball in one box), or empty boxes are allowed. The cells in the chart show the question that is answered by solving the formula given in the formula chart above.

Table of the 12 combinatorial objects - intuitive chart using balls and boxes

	Any Template:Mvar (no rules on placement)	Injective Template:Mvar (no multi-packs allowed)	Surjective Template:Mvar (no empty boxes allowed)
Template:Nowrap	[[#case f|Template:Mvar-sequence in Template:Mvar How many ways can you place Template:Mvar marked balls into Template:Mvar marked boxes, with no other rules on placement?]]	[[#case i|Template:Mvar-permutation in Template:Mvar How many ways can you place Template:Mvar marked balls into Template:Mvar marked boxes, with no multi-packs allowed?]]	[[#case s|composition of Template:Mvar with Template:Mvar subsets How many ways can you place Template:Mvar marked balls into Template:Mvar marked boxes, with no empty boxes allowed?]]
Template:Nowrap	[[#case fn|Template:Mvar-multisubset of Template:Mvar How many ways can you place Template:Mvar plain balls into Template:Mvar marked boxes, with no other rules on placement?]]	[[#case in|Template:Mvar-subset of Template:Mvar How many ways can you place Template:Mvar plain balls into Template:Mvar marked boxes, with no multi-packs allowed?]]	[[#case sn|composition of Template:Mvar with Template:Mvar terms How many ways can you place Template:Mvar plain balls into Template:Mvar marked boxes, with no empty boxes allowed?]]
Template:Nowrap	[[#case fx|partition of Template:Mvar into ≤ Template:Mvar subsets How many ways can you place Template:Mvar marked balls into Template:Mvar plain boxes, with no other rules on placement?]]	[[#case ix|partition of Template:Mvar into ≤ Template:Mvar elements How many ways can you place Template:Mvar marked balls into Template:Mvar plain boxes, with no multi-packs allowed?]]	[[#case sx|partition of Template:Mvar into Template:Mvar subsets How many ways can you place Template:Mvar marked balls into Template:Mvar plain boxes, with no empty boxes allowed?]]
Template:Nowrap	[[#case fnx|partition of Template:Mvar into ≤ Template:Mvar parts How many ways can you place Template:Mvar plain balls into Template:Mvar plain boxes, with no other rules on placement?]]	[[#case inx|partition of Template:Mvar into ≤ Template:Mvar parts 1 How many ways can you place Template:Mvar plain balls into Template:Mvar plain boxes, with no multi-packs allowed?]]	[[#case snx|partition of Template:Mvar into Template:Mvar parts How many ways can you place Template:Mvar plain balls into Template:Mvar plain boxes, with no empty boxes allowed?]]

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.

Template:Anchor Functions from Template:Mvar to Template:Mvar

This case is equivalent to counting sequences of Template:Mvar elements of Template:Mvar with no restriction: a function Template:Math is determined by the Template:Mvar images of the elements of Template:Mvar, which can each be independently chosen among the elements of Template:Mvar. This gives a total of Template:Mvar^{Template:Mvar} possibilities.

Example:

$X=\{a,b,c\},N=\{1,2\}\text{, then }$

$|\{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a),(c,b),(c,c)\}|=3^2=9$

Template:Anchor Injective functions from Template:Mvar to Template:Mvar

This case is equivalent to counting sequences of Template:Mvar distinct elements of Template:Mvar, also called Template:Mvar-permutations of Template:Mvar, or sequences without repetitions; again this sequence is formed by the Template:Mvar images of the elements of Template:Mvar. This case differs from the one of unrestricted sequences in that there is one choice fewer for the second element, two fewer for the third element, and so on. Therefore instead of by an ordinary power of Template:Mvar, the value is given by a falling factorial power of Template:Mvar, in which each successive factor is one fewer than the previous one. The formula is

$x^{\underset{\_}{n}}=x(x-1)\cdots (x-n+1).$

Note that if Template:Math then one obtains a factor zero, so in this case there are no injective functions Template:Math at all; this is just a restatement of the pigeonhole principle.

Example:

$X=\{a,b,c,d\},N=\{1,2\}\text{, then }$

$|\{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a),(c,b),(c,d),(d,a),(d,b),(d,c)\}|=4^{\underset{\_}{2}}=4\times 3=12$

Template:Anchor Injective functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

This case is equivalent to counting subsets with Template:Mvar elements of Template:Mvar, also called Template:Mvar-combinations of Template:Mvar: among the sequences of Template:Mvar distinct elements of Template:Mvar, those that differ only in the order of their terms are identified by permutations of Template:Mvar. Since in all cases this groups together exactly Template:Mvar! different sequences, we can divide the number of such sequences by Template:Mvar! to get the number of Template:Mvar-combinations of Template:Mvar. This number is known as the binomial coefficient $(\genfrac{}{}{0ex}{}{x}{n})$, which is therefore given by

$(\genfrac{}{}{0ex}{}{x}{n})=\frac{x^{\underset{\_}{n}}}{n!}=\frac{x(x-1)\cdots (x-n+2)(x-n+1)}{n(n-1)\cdots 2\cdot 1}.$

Example:

$X=\{a,b,c,d\},N=\{1,2\}\text{, then }$

$|\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\}\}|=\frac{4^{\underset{\_}{2}}}{2!}=\frac{4\times 3}{2}=6$

Template:Anchor Functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

This case is equivalent to counting multisets with Template:Mvar elements from Template:Mvar (also called Template:Mvar-multicombinations). The reason is that for each element of Template:Mvar it is determined how many elements of Template:Mvar are mapped to it by Template:Mvar, while two functions that give the same such "multiplicities" to each element of Template:Mvar can always be transformed into another by a permutation of Template:Mvar. The formula counting all functions Template:Math is not useful here, because the number of them grouped together by permutations of Template:Mvar varies from one function to another. Rather, as explained under combinations, the number of Template:Mvar-multicombinations from a set with Template:Mvar elements can be seen to be the same as the number of Template:Mvar-combinations from a set with Template:Math elements. This reduces the problem to another one in the twelvefold way, and gives as result

$(\genfrac{}{}{0ex}{}{x+n-1}{n})=\frac{(x+n-1)(x+n-2)\cdots (x+1)x}{n(n-1)\cdots 2\cdot 1}=\frac{x^{\bar{n}}}{n!}.$

Example:

$X=\{a,b,c\},N=\{1,2\}\text{, then }$

$|\{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\{c,c\}\}|=\frac{3^{\bar{2}}}{2!}=\frac{4\times 3}{2}=6$

Template:Anchor Surjective functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

This case is equivalent to counting multisets with Template:Mvar elements from Template:Mvar, for which each element of Template:Mvar occurs at least once. This is also equivalent to counting the compositions of Template:Mvar with Template:Mvar (non-zero) terms, by listing the multiplicities of the elements of Template:Mvar 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 Template:Mvar by Template:Mvar, the result is

$(\genfrac{}{}{0ex}{}{n-1}{n-x}).$

Note that when Template:Mvar < Template:Mvar there are no surjective functions Template:Math 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 same value is also given by the expression

$(\genfrac{}{}{0ex}{}{n-1}{x-1}),$

except in the extreme case Template:Math, where with the former expression correctly gives $(\genfrac{}{}{0ex}{}{-1}{0})=1$, while the latter incorrectly gives $(\genfrac{}{}{0ex}{}{-1}{-1})=0$.

The form of the result suggests looking for a manner to associate a class of surjective functions Template:Math directly to a subset of Template:Math elements chosen from a total of Template:Math, which can be done as follows. First choose a total ordering of the sets Template:Mvar and Template:Mvar, and note that by applying a suitable permutation of Template:Mvar, every surjective function Template:Math can be transformed into a unique weakly increasing (and of course still surjective) function. If one connects the elements of Template:Mvar in order by Template:Math arcs into a linear graph, then choosing any subset of Template:Math arcs and removing the rest, one obtains a graph with Template:Mvar connected components, and by sending these to the successive elements of Template:Mvar, one obtains a weakly increasing surjective function Template:Math; also the sizes of the connected components give a composition of Template:Mvar into Template:Mvar parts. This argument is basically the one given at stars and bars, except that there the complementary choice of Template:Math "separations" is made.

Example:

$X=\{a,b\},N=\{1,2,3\}\text{, then }$

$|\{\{a,a,b\},\{a,b,b\}\}|=(\genfrac{}{}{0ex}{}{3-1}{3-2})=(\genfrac{}{}{0ex}{}{2}{1})=\frac{2!}{1!\times (2-1)!}=2$

Template:Anchor Injective functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

In this case we consider sequences of Template:Mvar distinct elements from Template:Mvar, but identify those obtained from one another by applying to each element a permutation of Template:Mvar. It is easy to see that two different such sequences can always be identified: the permutation must map term Template:Mvar of the first sequence to term Template:Mvar 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 Template:Mvar and Template:Mvar at all is that the existence of any such sequences to begin with requires Template:Math, by the pigeonhole principle. The number is therefore expressed as $[n\le x]$, using the Iverson bracket.

Template:Anchor Injective functions from Template:Mvar to Template:Mvar, up to permutations of Template:Mvar and Template:Mvar

This case is reduced to the previous one: since all sequences of Template:Mvar distinct elements from Template:Mvar can already be transformed into each other by applying a permutation of Template:Mvar to each of their terms, also allowing reordering of the terms does not give any new identifications; the number remains $[n\le x]$.

Template:Anchor Surjective functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

This case is equivalent to counting partitions of Template:Mvar into Template:Mvar (non-empty) subsets, or counting equivalence relations on Template:Mvar with exactly Template:Mvar classes. Indeed, for any surjective function Template:Math, the relation of having the same image under Template:Mvar is such an equivalence relation, and it does not change when a permutation of Template:Mvar is subsequently applied; conversely one can turn such an equivalence relation into a surjective function by assigning the elements of Template:Mvar in some manner to the Template:Mvar equivalence classes. The number of such partitions or equivalence relations is by definition the Stirling number of the second kind Template:Mvar(Template:Mvar,Template:Mvar), also written $\{\genfrac{}{}{0ex}{}{n}{x}\}$. 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.

Template:Anchor Surjective functions from Template:Mvar to Template:Mvar

For each surjective function Template:Math, its orbit under permutations of Template:Mvar has Template:Mvar! elements, since composition (on the left) with two distinct permutations of Template:Mvar never gives the same function on Template:Mvar (the permutations must differ at some element of Template:Mvar, which can always be written as $f(i)$ for some Template:Mvar ∈ Template:Mvar, and the compositions will then differ at Template:Mvar). It follows that the number for this case is Template:Mvar! times the number for the previous case, that is $x!\{\genfrac{}{}{0ex}{}{n}{x}\}.$

Example:

$X=\{a,b\},N=\{1,2,3\}\text{, then }$

$|\{(a,a,b),(a,b,a),(a,b,b),(b,a,a),(b,a,b),(b,b,a)\}|=2!\left\{\genfrac{}{}{0ex}{}{3}{2}\right\}=2\times 3=6$

Template:Anchor Functions from Template:Mvar to Template:Mvar, up to a permutation of Template:Mvar

This case is like the corresponding one for surjective functions, but some elements of Template:Mvar might not correspond to any equivalence class at all (since one considers functions up to a permutation of Template:Mvar, it does not matter which elements are concerned, just how many). As a consequence one is counting equivalence relations on Template:Mvar with at most Template:Mvar classes, and the result is obtained from the mentioned case by summation over values up to Template:Mvar, giving ${\sum }_{k=0}^x\{\genfrac{}{}{0ex}{}{n}{k}\}$. In case Template:Mvar ≥ Template:Mvar, the size of Template:Mvar poses no restriction at all, and one is counting all equivalence relations on a set of Template:Mvar elements (equivalently all partitions of such a set); therefore ${\sum }_{k=0}^n\{\genfrac{}{}{0ex}{}{n}{k}\}$ gives an expression for the Bell number Template:Mvar_{Template:Mvar}.

Template:Anchor Surjective functions from Template:Mvar to Template:Mvar, up to permutations of Template:Mvar and Template:Mvar

This case is equivalent to counting partitions of the number Template:Mvar into Template:Mvar non-zero parts. Compared to the case of counting [[#case sx|surjective functions up to permutations of Template:Mvar]] only ($\{\genfrac{}{}{0ex}{}{n}{x}\}$), one only retains the sizes of the equivalence classes that the function partitions Template:Mvar into (including the multiplicity of each size), since two equivalence relations can be transformed into one another by a permutation of Template:Mvar if and only if the sizes of their classes match. This is precisely what distinguishes the notion of partition of Template:Mvar from that of partition of Template:Mvar, so as a result one gets by definition the number Template:Mvar_{Template:Mvar}(Template:Mvar) of partitions of Template:Mvar into Template:Mvar non-zero parts.

Template:Anchor Functions from Template:Mvar to Template:Mvar, up to permutations of Template:Mvar and Template:Mvar

This case is equivalent to counting partitions of the number Template:Mvar into ≤ Template:Mvar parts. The association is the same as for the previous case, except that now some parts of the partition may be equal to 0. (Specifically, they correspond to elements of Template:Mvar not in the image of the function.) Each partition of Template:Mvar into at most Template:Mvar non-zero parts can be extended to such a partition by adding the required number of zeroes, and this accounts for all possibilities exactly once, so the result is given by ${\sum }_{k=0}^x{p}_k(n)$. By adding 1 to each of the Template:Mvar parts, one obtains a partition of Template:Math into Template:Mvar nonzero parts, and this correspondence is bijective; hence the expression given can be simplified by writing it as $p_x(n+x)$.

Extremal cases

The above formulas give the proper values for all finite sets Template:Mvar and Template:Mvar. 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 Template:Mvar or Template:Mvar are empty. The following considerations apply to such cases.

• For every set Template:Mvar there is exactly one function from the empty set to Template:Mvar (there are no values of this function to specify), which is always injective, but never surjective unless Template:Mvar is (also) empty.
• For every non-empty set Template:Mvar there are no functions from Template:Mvar to the empty set (there is at least one value of the function that must be specified, but it cannot).
• When Template:Math there are no injective functions Template:Math, and if Template:Math there are no surjective functions Template:Math.
• The expressions used in the formulas have as particular values

$0^0=0^{\underset{\_}{0}}=0!=(\genfrac{}{}{0ex}{}{0}{0})=(\genfrac{}{}{0ex}{}{-1}{0})=\left\{\genfrac{}{}{0ex}{}{0}{0}\right\}=p_0(0)=1$

(the first three are instances of an empty product, and the value $(\genfrac{}{}{0ex}{}{-1}{0})=\frac{(-1{)}^{\underset{\_}{0}}}{0!}=1$ is given by the conventional extension of binomial coefficients to arbitrary values of the upper index), while

$\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}=p_x(n)=0\text{whenever either }n>0=x\text{ or }0\le n<x.$

In particular in the case of counting multisets with Template:Mvar elements taken from Template:Mvar, the given expression $(\genfrac{}{}{0ex}{}{n+x-1}{n})$ is equivalent in most cases to $(\genfrac{}{}{0ex}{}{n+x-1}{x-1})$, but the latter expression would give 0 for the case Template:Math (by the usual convention that binomial coefficients with a negative lower index are always 0). Similarly, for the case of counting compositions of Template:Mvar with Template:Mvar non-zero parts, the given expression $(\genfrac{}{}{0ex}{}{n-1}{n-x})$ is almost equivalent to the expression $(\genfrac{}{}{0ex}{}{n-1}{x-1})$ given by the stars and bars argument, but the latter gives incorrect values for Template:Math and all values of Template:Mvar. For the cases where the result involves a summation, namely those of counting [[#case fx|partitions of Template:Mvar]] into at most Template:Mvar non-empty subsets or [[#case fx|partitions of Template:Mvar]] into at most Template:Mvar non-zero parts, the summation index is taken to start at 0; although the corresponding term is zero whenever Template:Math, it is the unique non-zero term when Template:Math, 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 groups of permutations to act on Template:Mvar and Template:Mvar. If Template:Mvar is a group of permutations of Template:Mvar, and Template:Mvar is a group of permutations of Template:Mvar, then we count equivalence classes of functions $f:N\to X$. Two functions Template:Mvar and Template:Mvar are considered equivalent if, and only if, there exist $g\in G,h\in H$ so that $F=h\circ f\circ g$. This extension leads to notions such as cyclic and dihedral permutations, as well as cyclic and dihedral partitions of numbers and sets.

The twentyfold way

Another generalization called the twentyfold way was developed by Kenneth P. Bogart in his book "Combinatorics Through Guided Discovery". In the problem of distributing objects to boxes both the objects and the boxes may be identical or distinct. Bogart identifies 20 cases. Robert A. Proctor has constructed the thirtyfold way.

The twentyfold way; models for distribution of Template:Mvar objects among Template:Mvar recipients

№	Objects	Condition of distribution	Recipients
			Distinct	Identical
1	Template:Rh rowspan="4" | Distinct	Template:Rh | No restriction	[[#case f|Template:Mvar-sequence in Template:Mvar]] $x^n$	[[#case fx|partition of Template:Mvar into ≤ Template:Mvar subsets]] $\sum _{i=0}^x\left\{\genfrac{}{}{0ex}{}{n}{i}\right\}$
Template:Rh | 2	Template:Rh | At most one each	[[#case i|Template:Mvar-permutation of Template:Mvar]] $x^{\underset{\_}{n}}$	$\{\begin{array}{cc}1& \text{if }n\le x\\ 0& \text{otherwise}\end{array}$
Template:Rh | 3	Template:Rh | At least one each	[[#case s|composition of Template:Mvar with Template:Mvar subsets]] $x!\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$	[[#case sx|partition of Template:Mvar into Template:Mvar subsets]] $\left\{\genfrac{}{}{0ex}{}{n}{x}\right\}$
Template:Rh | 4	Template:Rh | Exactly one each	$n!=x!$ permutations	$\{\begin{array}{cc}1& \text{if }n=x\\ 0& \text{otherwise}\end{array}$
Template:Rh | 5	Template:Rh rowspan="2" | Distinct, ordered	Template:Rh | No restriction	$(n+x-1{)}^{\underset{\_}{n}}$ ordered functions	$\sum _{i=1}^{x}L(n,i)$ broken permutations ($\le x$ parts) Where $L(n,i)$ is the Lah number
Template:Rh | 6	Template:Rh | At least one each	$(n{)}^{\underset{\_}{x}}(n-1{)}^{\underset{\_}{n-x}}$ ordered onto functions	$L(n,x)=\left(\genfrac{}{}{0ex}{}{n}{x}\right)(n-1{)}^{\underset{\_}{n-x}}$ broken permutations (Template:Mvar parts) Where $L(n,x)$ is the Lah number
Template:Rh | 7	Template:Rh rowspan="4" | Identical	Template:Rh | No restriction	[[#case fn|Template:Mvar-multisubset of Template:Mvar]] $\left(\genfrac{}{}{0ex}{}{x+n-1}{n}\right)$	$\sum _{i=1}^x{p}_i(n)$ number partitions ($\le x$ parts)
Template:Rh | 8	Template:Rh | At most one each	[[#case in|Template:Mvar-subset of Template:Mvar]] $\left(\genfrac{}{}{0ex}{}{x}{n}\right)$	$\{\begin{array}{cc}1& \text{if }n\le x\\ 0& \text{otherwise}\end{array}$
Template:Rh | 9	Template:Rh | At least one each	$\left(\genfrac{}{}{0ex}{}{n-1}{x-1}\right)$ compositions (Template:Mvar parts)	[[#case snx|partition of Template:Mvar into Template:Mvar parts]] $p_x(n)$
Template:Rh | 10	Template:Rh | Exactly one each	$\{\begin{array}{cc}1& \text{if }n=x\\ 0& \text{otherwise}\end{array}$	$\{\begin{array}{cc}1& \text{if }n=x\\ 0& \text{otherwise}\end{array}$

See also

• Stars and bars (combinatorics)