In
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of
counting
Counting is the process of determining the number of elements of a finite set of objects, i.e., determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for every ele ...
permutations
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pr ...
,
combinations
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are t ...
,
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s, and partitions either
of a set or
of a number. The idea of the classification is credited to
Gian-Carlo Rota
Gian-Carlo Rota (April 27, 1932 – April 18, 1999) was an Italian-American mathematician and philosopher. He spent most of his career at the Massachusetts Institute of Technology, where he worked in combinatorics, functional analysis, pro ...
, and the name was suggested by
Joel Spencer
Joel Spencer (born April 20, 1946) 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 supervi ...
.
Overview
Let and be
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
s. Let
and
be the
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
of the sets. Thus is an -set, and is an -set.
The general problem we consider is the enumeration of
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es of
functions .
The functions are subject to one of the three following restrictions:
# No condition: each in may be sent by to any in , and each may occur multiple times.
# is
injective
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
: each value
for in must be distinct from every other, and so each in may occur at most once in the
image
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
of .
# is
surjective
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
: for each in there must be at least one in such that
, thus each will occur at least once in the image of .
(The condition " is
bijective
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...
" is only an option when
; but then it is equivalent to both " is injective" and " is surjective".)
There are four different
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s which may be defined on the set of functions from to :
# equality;
# equality
up to Two Mathematical object, mathematical objects ''a'' and ''b'' are called equal up to an equivalence relation ''R''
* if ''a'' and ''b'' are related by ''R'', that is,
* if ''aRb'' holds, that is,
* if the equivalence classes of ''a'' and ''b'' wi ...
a
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or proc ...
of ;
# equality up to a permutation of ;
# equality up to permutations of and .
The three conditions on the functions and the four equivalence relations can be paired in 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
In mathematics, Stirling numbers arise in a variety of analytic and combinatorial problems. They are named after James Stirling, who introduced them in a purely algebraic setting in his book ''Methodus differentialis'' (1730). They were rediscove ...
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.e.,
partial permutation In combinatorial mathematics, a partial permutation, or sequence without repetition, on a finite set ''S''
is a bijection between two specified subsets of ''S''. That is, it is defined by two subsets ''U'' and ''V'' of equal size, and a one-to-one ...
s or sequences without repetition) of ''X'' is equivalent to counting
injective functions .
* Counting ''n''-combinations of ''X'' is equivalent to counting
injective functions up to permutations of ''N''.
* Counting permutations of the set ''X'' is equivalent to counting injective functions when ''n'' = x, and also to counting
surjective functions when .
* Counting multisets of size ''n'' (also known as ''n''-combinations with repetitions) of elements in ''X'' is equivalent to counting all
functions up to permutations of ''N''.
* Counting partitions of the set ''N'' into ''x'' subsets is equivalent to counting all
surjective functions up to permutations of ''X''.
* Counting
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
s of the number ''n'' into ''x'' parts is equivalent to counting all
surjective functions up to permutations of ''N''.
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 ''N'' can be identified with a set of balls, and ''X'' with a set of boxes; the function ''ƒ'' : then describes a way to distribute the balls into the boxes, namely by putting each ball ''a'' into box ''ƒ''(''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 ''ƒ'' 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 permutations of ''N'' or ''X'' 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
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
. Imagine a population of ''X'' items (or people), of which we choose ''N''. Two different schemes are normally described, known as "
sampling with replacement
In statistics, a simple random sample (or SRS) is a subset of individuals (a sample) chosen from a larger set (a population) in which a subset of individuals are chosen randomly, all with the same probability. It is a process of selecting a sample ...
" and "
sampling without replacement
In statistics, a simple random sample (or SRS) is a subset of individuals (a sample) chosen from a larger set (a population) in which a subset of individuals are chosen randomly, all with the same probability. It is a process of selecting a sample ...
". 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
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independ ...
of all the other choices, and the set of samples is technically referred to as
independent identically distributed
In probability theory and statistics, a collection of random variables is independent and identically distributed if each random variable has the same probability distribution as the others and all are mutually independent. This property is us ...
. In the latter case, however, once we've chosen an item, we put it aside so that we can't choose it again. This means that the act of choosing an item has an effect on all the following choices (the particular item can't 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. (Another way to think of this is to sort each choice by the item number, and throw out any duplicates that result.)
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 "S
''n'' 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
In probability theory and statistics, a probability distribution is the mathematical function that gives the probabilities of occurrence of different possible outcomes for an experiment. It is a mathematical description of a random phenomenon ...
. Sampling with replacement where ordering matters is comparable to describing the
joint distribution
Given two random variables that are defined on the same probability space, the joint probability distribution is the corresponding probability distribution on all possible pairs of outputs. The joint distribution can just as well be considered ...
of ''N'' separate
random variable
A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
s, each with an ''X''-fold
categorical distribution
In probability theory and statistics, a categorical distribution (also called a generalized Bernoulli distribution, multinoulli distribution) is a discrete probability distribution that describes the possible results of a random variable that can ...
. Sampling with replacement where ordering doesn't matter, however, is comparable to describing a single
multinomial distribution
In probability theory, the multinomial distribution is a generalization of the binomial distribution. For example, it models the probability of counts for each side of a ''k''-sided dice rolled ''n'' times. For ''n'' independent trials each of w ...
of ''N'' draws from an ''X''-fold category, where only the number seen of each category matters. Sampling without replacement where ordering doesn't matter is comparable to a single
multivariate hypergeometric distribution
In probability theory and statistics, the hypergeometric distribution is a discrete probability distribution that describes the probability of k successes (random draws for which the object drawn has a specified feature) in n draws, ''without'' ...
. Sampling without replacement where order does matter does not seem to correspond to a probability distribution. Note that in all the "injective" cases (i.e. sampling without replacement), the number of sets of choices is zero unless . ("Comparable" in the above cases means that each element of the
sample space
In probability theory, the sample space (also called sample description space, possibility space, or outcome space) of an experiment or random trial is the set of all possible outcomes or results of that experiment. A sample space is usually den ...
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've chosen each item at least once. Then, we count how many choices we've made, and if it's not equal to ''N'', throw out the entire set and repeat. This is vaguely comparable to the
coupon collector's problem
In probability theory, the coupon collector's problem describes "collect all coupons and win" contests. It asks the following question: If each box of a brand of cereals contains a coupon, and there are ''n'' different types of coupons, what is th ...
, where the process involves "collecting" (by sampling with replacement) a set of ''X'' coupons until each coupon has been seen at least once. Note that in all "surjective" cases, the number of sets of choices is zero unless .
Labelling, selection, grouping
A function ''ƒ'' : can be considered from 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 from ''X'' 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).
When viewing ''ƒ'' as an unordered selection of the elements of ''X'', 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
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
. Without the requirement, one and the same element of ''X'' may occur multiple times in the selection, and the result is a
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
of size ''n'' of elements from ''X'', also called an ''n''-
multicombination
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
or ''n''-combination with repetition.
The requirement that ''ƒ'' be surjective, from the viewpoint of labelling elements of ''N'', means that every label is to be used at least once; from the viewpoint of selection from ''X'', it means that every element of ''X'' must be included in the selection at least once. Labelling with surjection is equivalent to a grouping of elements of ''N'' followed by labeling each group by an element of ''X'', and is accordingly somewhat more complicated to describe mathematically.
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 may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of the number ''n'', into exactly ''x'' (for surjective ''ƒ'') or at most ''x'' (for arbitrary ''ƒ'') 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 particular notations used are:
* the
falling factorial power
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
:\begin
(x)_n = x^\underline &= \overbrace^ \\
&= \prod_^n(x-k+1) = \prod_^(x-k) \,.
\e ...
,
* the
rising factorial power
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
:\begin
(x)_n = x^\underline &= \overbrace^ \\
&= \prod_^n(x-k+1) = \prod_^(x-k) \,.
\e ...
,
* the
factorial
In mathematics, the factorial of a non-negative denoted is the product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times (n-1) \times (n-2) \t ...
* the
Stirling number of the second kind
In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to Partition of a set, partition a set of ''n'' objects into ''k'' non-empty subsets and is denoted by S(n,k) ...
, denoting the number of ways to
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
a set of ''n'' elements into ''k'' subsets
* the
binomial coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
* the
Iverson bracket encoding a truth value as 0 or 1
* the number
of
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
s of ''n'' into ''k'' 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 ''X'' numbered items (numbered from 1 to ''x''), from which we choose ''n'', yielding an ordered list of the items: e.g. if there are
items of which we choose
, 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 ''f'': After we choose an item, we put it back, so we might choose it again.
; Injective ''f'': After we choose an item, we set it aside, so we can't choose it again; hence we'll end up with ''n'' distinct items. Necessarily, then, unless
, no lists can be chosen at all.
; Surjective ''f'': 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
, no lists can be chosen at all.
And the rows mean:
; Distinct: Leave the lists alone; count them directly.
; S
''n'' 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).
; S
''x'' 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).
; S
''n'' × S
''x'' 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.
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 ''x''
''n'' possibilities.
Example:
Injective function
In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositiv ...
s 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 fewer for the second element, two fewer 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
In mathematics, the falling factorial (sometimes called the descending factorial, falling sequential product, or lower factorial) is defined as the polynomial
:\begin
(x)_n = x^\underline &= \overbrace^ \\
&= \prod_^n(x-k+1) = \prod_^(x-k) \,.
\e ...
of ''x'', in which each successive factor is one fewer than the previous one. The formula is
:
Note that if 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
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...
.
Example:
Injective functions from ''N'' to ''X'', up to a permutation of ''N''
This case is equivalent to counting subsets with ''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 coefficient
In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers and is written \tbinom. It is the coefficient of the t ...
, which is therefore given by
:
Example:
Functions from ''N'' to ''X'', up to a permutation of ''N''
This case is equivalent to counting
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s with ''n'' elements from ''X'' (also called ''n''-multicombinations). 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
In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are t ...
, 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
:
Example:
Surjective functions from ''N'' to ''X'', up to a permutation of ''N''
This case is equivalent to counting
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
s with ''n'' elements from ''X'', for which each element of ''X'' occurs at least once. This is also equivalent to counting the
compositions
Composition or Compositions may refer to:
Arts and literature
* Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
of ''n'' with ''x'' (non-zero) terms, 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 same value is also given by the expression
:
except in the extreme case , where with the former expression correctly gives
, while the latter incorrectly gives
.
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
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
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
In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two terminal ...
, 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.
Example:
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 , by the pigeonhole principle. The number is therefore expressed as