In
combinatoricsCombinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...
, a branch of
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, the
twelvefold way provides a unified framework for
countA count is a nobleman in European countries; his wife is a countess. The word count came into English from the French comte, itself from Latin comes—in its accusative comitem—meaning "companion", and later "companion of the emperor, delegate of the emperor". The British equivalent is an earl...
ing permutations, combinations and
partitionsIn 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...
.
Let
N and
X be
finiteIn mathematics, finite set is a set that has a finite number of elements. For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set. A set that is not finite is called infinite...
sets. Let
n = |
N| and
x = |
X|.
Thus
N is an
n-set, and
X is an
x-set.
The general
problemA problem is an issue or obstacle which makes it difficult to achieve a desired goal, objective or purpose. It refers to a situation, condition, or issue that is yet unresolved...
we consider is the enumeration of
functionsIn mathematics, a function is a relation between a given set of elements and another set of elements , which associates each element in the domain with exactly one element in the codomain...
from
N to
X.
There are three different
conditionsThe material conditional, also known as the material implication or truth functional conditional, expresses a property of certain conditionals in logic. In propositional logic, it expresses a binary truth function from truth-values to truth-values. In predicate logic, it can be viewed as a subset...
which may be imposed upon
ƒ :
N →
X.
- no condition;
- ƒ is injective;
- ƒ is surjective.
There are four different
equivalence relationIn mathematics, an equivalence relation is, loosely, a binary relation on a set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets...
s which may be imposed upon the set of functions
from
N to
X.
- equality;
- equality up to
In mathematics, the phrase "up to xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e. one to which it is considered equivalent...
a permutation of N;
- equality up to a permutation of X;
- equality up to permutations of N and X.
These criteria can be paired in 3 × 4 = 12 ways.
A function
ƒ :
N →
X admits two different combinatorial interpretations.
- ƒ selects elements
In mathematics, an element or member of a set is any one of the distinct objects that make up that set.- Sets :Writing A = {1, 2, 3, 4 }, means that the elements of the set A are the numbers 1, 2, 3 and 4. Sets of elements of A, for example {1, 2}, are...
from the set X.
In
combinatoricsCombinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...
, a branch of
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, the
twelvefold way provides a unified framework for
countA count is a nobleman in European countries; his wife is a countess. The word count came into English from the French comte, itself from Latin comes—in its accusative comitem—meaning "companion", and later "companion of the emperor, delegate of the emperor". The British equivalent is an earl...
ing permutations, combinations and
partitionsIn 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...
.
Let
N and
X be
finiteIn mathematics, finite set is a set that has a finite number of elements. For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set. A set that is not finite is called infinite...
sets. Let
n = |
N| and
x = |
X|.
Thus
N is an
n-set, and
X is an
x-set.
The general
problemA problem is an issue or obstacle which makes it difficult to achieve a desired goal, objective or purpose. It refers to a situation, condition, or issue that is yet unresolved...
we consider is the enumeration of
functionsIn mathematics, a function is a relation between a given set of elements and another set of elements , which associates each element in the domain with exactly one element in the codomain...
from
N to
X.
There are three different
conditionsThe material conditional, also known as the material implication or truth functional conditional, expresses a property of certain conditionals in logic. In propositional logic, it expresses a binary truth function from truth-values to truth-values. In predicate logic, it can be viewed as a subset...
which may be imposed upon
ƒ :
N →
X.
- no condition;
- ƒ is injective;
- ƒ is surjective.
There are four different
equivalence relationIn mathematics, an equivalence relation is, loosely, a binary relation on a set that specifies how to split up the set into subsets such that every element of the larger set is in exactly one of the subsets...
s which may be imposed upon the set of functions
from
N to
X.
- equality;
- equality up to
In mathematics, the phrase "up to xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e. one to which it is considered equivalent...
a permutation of N;
- equality up to a permutation of X;
- equality up to permutations of N and X.
These criteria can be paired in 3 × 4 = 12 ways.
Selection versus partition
A function
ƒ :
N →
X admits two different combinatorial interpretations.
- ƒ selects elements
In mathematics, an element or member of a set is any one of the distinct objects that make up that set.- Sets :Writing A = {1, 2, 3, 4 }, means that the elements of the set A are the numbers 1, 2, 3 and 4. Sets of elements of A, for example {1, 2}, are...
from the set X. The selection is indexedThe word index is used in variety of senses in mathematics.* In perhaps the most frequent sense, an index is a superscript or subscript to a symbol. Superscript indices are often, but not always, used to indicate powers. Subscript indices are usually used to identify an element of a set or array...
by N.
- ƒ partitions N into x disjoint subsets, labeled by the elements of X.
Ordered selections and partitions
If
ƒ is injective, then
ƒ does not select any element more than once.
In this case we say that
ƒ selects elements
without repetition.
If
ƒ is not required to be injective, then we say that repetition is allowed.
If
ƒ is surjective, then every element of
X labels a non-empty
subsetIn mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. Notice that A and B may coincide...
of
N. In this case we say that
ƒ is a partition of
N into
x parts.
If
ƒ is not required to be surjective, then we say that
ƒ partitions
N into at most
x parts.
Unordered selections
We interpret a function
ƒ :
N →
X as a selection from
X.
The elements of
X are said to be
indistinguishable if we do not distinguish between two selections that differ by a permutation of
X.
Formally, an
unordered selection is an
equivalence classIn mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a:...
of functions
ƒ :
N →
X. Two functions
ƒ and
F represent the same
unorderedIn mathematics, an ordered pair is a collection of objects having two coordinates , such that one can always uniquely determine the object, which is the first coordinate of the pair as well as the second coordinate...
selection
if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements. In that it is biconditional, the connective can be likened to the standard material conditional combined with its reverse ; hence the name...
there exists a
bijectionIn mathematics, a bijection, or a bijective function is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y and no unmapped element remains in both X and Y.Alternatively, f is bijective if it is a one-to-one correspondence...
h :
N →
N
such that .
Ordered selections are often called "permutations", and unordered
selections are often called "combinations". The word "permutation"
has a second meaning: namely, a bijection from
a set to itself. We hope that this dual usage is not unduly confusing.
Unordered partitions
We also interpret a function
ƒ :
N →
X as a partition
of
N. The elements of
N are said to be
indistinguishable
if we do not distinguish between two partitions that differ by a permutation of
N.
If the elements of
N are indistinguishable,
then we usually speak of partitions of , rather than of an
N-set.
Formally, an unordered partition is an equivalence class of functions
ƒ :
N →
X. Two functions
ƒ and
F represent the same unordered partition if and only if there exists a bijection
h :
X →
X so that .
Balls and boxes
Placing "balls" in "boxes" is a useful metaphor for counting problems. We think of
N as the set of balls, and
X as the set of boxes. The balls may be either distinguishable or indistinguishable, and the same is
trueTrue is the adjectival form of the word truth.True may also refer to:-In business:*True Corporation, a Thai communications group whose subsidiaries include True Internet, True Move and True Visions-In music:*"True"...
of the boxes.
Injectivity of
ƒ means that no box may contain more than one ball. Surjectivity of
ƒ means that each box will contain at least one ball.
Formulas
-
- n-permutations of an x-set with repetition allowed.
- Functions from to X, up to
In mathematics, the phrase "up to xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e. one to which it is considered equivalent...
a permutation of
-
- n-combinations of an x-set with repetition allowed.
- Functions from N to X, up to a permutation of X
-
- Unordered partitions of an -set into at most x parts.
-
-
- where the are Stirling numbers of the second kind
In mathematics, Stirling numbers of the second kind, together with Stirling numbers of the first kind, are one of the two types of Stirling numbers. They commonly occur in the study of combinatorics, where they count the number of partitions. The Stirling numbers of the first and second kind can be...
.
- Functions from N to X, up to permutations of N and X
-
- Unordered partitions of n into at most x parts.
-
-
- where is the number of partitions
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 k parts.
- Injective functions from N to X
-
- n-permutations of an x-set, without repetition.
-
- Injective functions from N to X, up to a permutation of N
-
- n-combinations of an x-set, without repetition.
-
- Injective functions from N to X, up to a permutation of X
-
- Injective functions from N to X, up to permutations of N and X
-
- Surjective functions from N to X
-
- Ordered partitions of an n-set into x parts.
-
- Surjective functions from N to X, up to a permutation of N
-
- Ordered partitions of n into x parts.
-
- Surjective functions from N to X, up to a permutation of X
-
- Unordered partitions of an n-set into x parts.
-
- Surjective functions from N to X, up to permutations of N and X
-
- Unordered partitions of n into x parts.
-
Generalizations
We can generalize further by allowing other
groupsIn 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
cyclicA cyclic permutation is 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
dihedralDihedral Angle is the upward angle from horizontal of the wings or tailplane of a fixed-wing aircraft. Anhedral Angle is the name given to negative Dihedral Angle, that is, when there is a downward angle from horizontal of the wings or tailplane of a fixed-wing aircraft.Dihedral Angle has a...
permutations, as well as cyclic and dihedral partitions of
numberA number is a mathematical object used in counting and measuring. A notational symbol which represents a number is called a numeral, but in common usage the word number is used for both the abstract object and the symbol, as well as for the word for the number...
s and sets.