![]() | ||
In mathematics, a multiset (or bag) is a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements. For example, {a, a, b} and {a, b} are different multisets although they are the same set. However, order does not matter, so {a, a, b} and {a, b, a} are the same multiset.
Contents
- Overview
- History
- Example multisets
- Formal definition
- Multiplicity function
- Example multiset operations
- Free commutative monoids
- Counting multisets
- Recurrence relation
- Generalization and connection to the negative binomial series
- Polynomial notation
- Cumulant generating function
- Applications
- Generalizations
- References
The multiplicity of an element is the number of instances of the element in a specific multiset. For example, an infinite number of multisets exist which contain only elements a and b, varying only by multiplicity:
Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth. However, the use of multisets predates the word multiset by many centuries. Knuth attributes the first study of multisets to the Indian mathematician Bhāskarāchārya, who described permutations of multisets around 1150. Knuth also lists other names that were proposed or used for multisets, including list, bunch, bag, heap, sample, weighted set, collection, and suite.
Overview
The number of times an element belongs to the multiset is the multiplicity of that member. The total number of elements in a multiset, including repeated memberships, is the cardinality of the multiset. For example, in the multiset {a, a, b, b, b, c} the multiplicities of the members a, b, and c are respectively 2, 3, and 1, and the cardinality of the multiset is 6. To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset {2, 2, 3} can be represented as [2, 2, 3]. In multisets, as in sets and in contrast to tuples, the order of elements is irrelevant: The multisets {a, a, b} and {a, b, a} are equal.
History
Wayne Blizard traced multisets back to the very origin of numbers, arguing that “in ancient times, the number n was often represented by a collection of n strokes, tally marks, or units.” These and similar collections of objects are multisets as strokes, tally marks, or units are considered indistinguishable. This shows that people implicitly used multisets even before mathematics emerged.
This shows that necessity in this structure has been always so urgent that multisets have been several times rediscovered and appeared in literature under different names. For instance, they were referred to as bags by James Lyle Peterson in 1981, who attributed this term to a 1971 paper by Cerf et al. A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set).
Although multisets were implicitly utilized from ancient times, their explicit exploration happened much later. The first known study of multisets is attributed to the Indian mathematician Bhāskarāchārya circa 1150, who described permutations of multisets. The work of Marius Nizolius (1498–1576) contains another early reference to the concept of multisets. Athanasius Kircher found the number of multiset permutations when one element can be repeated. Jean Prestet published a general rule for multiset permutations in 1675. John Wallis explained this rule in more detail in 1685.
In the explicit form, multisets appeared in the work of Richard Dedekind. Other mathematicians formalized multisets and began to study them as a precise mathematical object (structure) in the 20th century.
Example multisets
One of the simplest and most natural examples is the multiset of prime factors of a number n. Here the underlying set of elements is the set of prime divisors of n. For example, the number 120 has the prime factorization
which gives the multiset {2, 2, 2, 3, 5}.
A related example is the multiset of solutions of an algebraic equation. A quadratic equation, for example, has two solutions. However, in some cases they are both the same number. Thus the multiset of solutions of the equation could be {3, 5}, or it could be {4, 4}. In the latter case it has a solution of multiplicity 2.
A special case of the above are the eigenvalues of a matrix, if these are defined as the multiset of roots of its characteristic polynomial. However a choice is made here: the (usual) definition of eigenvalues does not refer to the characteristic polynomial, and other possibilities give rise to different notions of multiplicity, and therefore to different multisets. The geometric multiplicity of λ as eigenvalue of a matrix A is the dimension of the kernel of A − λI, which is often smaller than its multiplicity as root of the characteristic polynomial (the algebraic multiplicity) when the latter is larger than 1. The set of eigenvalues of A is also the set of roots of its minimal polynomial, but the multiset of those roots need not be the same either as the one defined using algebraic multiplicity, or using the geometric multiplicity.
Formal definition
Within set theory, a multiset may be formally defined as a 2-tuple (A, m) where A is some set and
The concept of a multiset is a generalization of the concept of a set. A multiset corresponds to an ordinary set if the multiplicity of every element is one (as opposed to some larger natural number). An indexed family, (ai), where i is in some index-set, may define a multiset, sometimes written {ai}, in which the multiplicity of any element x is the number of indices i such that
It is possible to extend the definition of a multiset by allowing multiplicities of individual elements to be infinite cardinals instead of natural numbers. Not all properties carry over to this generalization however, and this article uses the definition above, with finite multiplicities.
Multiplicity function
The set indicator function of a normal set is generalized to the multiplicity function for multisets. The set indicator function of a subset A of a set X is the function
defined by
The set indicator function of the intersection of sets is the minimum function of the indicator functions
The set indicator function of the union of sets is the maximum function of the indicator functions
The set indicator function of the set difference of sets is the zero-truncated subtraction of the indicator functions
The set indicator function of a subset is smaller than or equal to that of the superset
The set indicator function of a cartesian product is the product of the indicator functions of the cartesian factors
The cardinality of a (finite) set is the sum of the indicator function values
Now generalize the concept of set indicator function by releasing the constraint that the values are 0 and 1 only and allow the values 2, 3, 4 and so on. The resulting function is called a multiplicity function and such a function defines a multiset. The concepts of intersection, union, difference, subset, cartesian product and cardinality of multisets are defined by the above formulas. There are also the following additional operations.
The multiplicity function of a multiset sum, is the sum of the multiplicity functions
The scalar multiplication of a multiset by a natural number n may be defined as:
Example multiset operations
These examples demonstrate these operations of multiplicity functions.
Free commutative monoids
The free commutative monoid on a set X (see free object) can be taken to be the set of finite multisets with elements drawn from X, with the monoid operation being multiset sum and the empty multiset as identity element. Such monoids are also known as (finite) formal sums of elements of X with natural coefficients. The free commutative semigroup is the subset of the free commutative monoid which contains all multisets with elements drawn from X except the empty multiset.
Free abelian groups are formal sums (i.e. linear combinations) of elements of X with integer coefficients. Equivalently, they may be seen as signed finite multisets with elements drawn from X.
Counting multisets
The number of multisets of cardinality k, with elements taken from a finite set of cardinality n, is called the multiset coefficient or multiset number. This number is written by some authors as
The value of multiset coefficients can be given explicitly as
where the second expression is as a binomial coefficient; many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality k in a set of cardinality n + k − 1. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a rising factorial power
to match the expression of binomial coefficients using a falling factorial power:
There are for example 4 multisets of cardinality 3 with elements taken from the set {1, 2} of cardinality 2 (n = 2, k = 3), namely {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, {2, 2, 2}. There are also 4 subsets of cardinality 3 in the set {1, 2, 3, 4} of cardinality 4 (n + k − 1), namely {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}.
One simple way to prove the equality of multiset coefficients and binomial coefficients given above, involves representing multisets in the following way. First, consider the notation for multisets that would represent {a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d} (6 as, 2 bs, 3 cs, 7 ds) in this form:
This is a multiset of cardinality k = 18 made of elements of a set of cardinality n = 4. The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1. The number of vertical lines is 4 − 1. The number of multisets of cardinality 18 is then the number of ways to arrange the 4 − 1 vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 in a set of cardinality 18 + 4 − 1. Equivalently, it is the number of ways to arrange the 18 dots among the 18 + 4 − 1 characters, which is the number of subsets of cardinality 18 of a set of cardinality 18 + 4 − 1. This is
thus is the value of the multiset coefficient and its equivalencies:
One may define a generalized binomial coefficient
in which n is not required to be a nonnegative integer, but may be negative or a non-integer, or a non-real complex number. (If k = 0, then the value of this coefficient is 1 because it is the empty product.) Then the number of multisets of cardinality k in a set of cardinality n is
Recurrence relation
A recurrence relation for multiset coefficients may be given as
with
The above recurrence may be interpreted as follows. Let [n] :=
Now, consider the case in which n,k > 0. A multiset of cardinality k with elements from [n] might or might not contain any instance of the final element n. If it does appear, then by removing n once, one is left with a multiset of cardinality k − 1 of elements from [n], and every such multiset can arise, which gives a total of
If n does not appear, then our original multiset is equal to a multiset of cardinality k with elements from [n − 1], of which there are
Thus,
Generalization and connection to the negative binomial series
The multiplicative formula allows the definition of multiset coefficients to be extended by replacing n by an arbitrary number α (negative, real, complex):
With this definition one has a generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the
This Taylor series formula is valid for all complex numbers α and X with | X | < 1. It can also be interpreted as an identity of formal power series in X, where it actually can serve as definition of arbitrary powers of series with constant coefficient equal to 1; the point is that with this definition all identities hold that one expects for exponentiation, notably
and formulas such as these can be used to prove identities for the multiset coefficients.
If α is a nonpositive integer n, then all terms with k > −n are zero, and the infinite series becomes a finite sum. However, for other values of α, including positive integers and rational numbers, the series is infinite.
Polynomial notation
The set {x} may be represented by the monomial x. Its power set, {{}, {x}}, is represented by the binomial 1 + x.
The set {x, y} may be represented by the monomial xy. Its power set, {{}, {x}, {y}, {x, y}}, is represented by the polynomial
The multiset {x, x} may be represented by the monomial x2. The multiset of submultisets of {x, x}, {{}, {x}, {x}, {x, x}}, is represented by the polynomial
The multiset of submultisets of the multiset represented by the polynomial xn is
That is why the binomial coefficient counts the number of k-combinations of an n-set.
The multiset represented by the polynomial xKyN − K, containing N elements, K of which are hits, is called a statistical population, and a submultiset is called a statistical sample. The set of samples is
which by the binomial theorem equals
So the number of n-samples with k hits is
See hypergeometric distribution and inferential statistics for further on the distribution of hits.
The infinite set of finite multisets of elements taken from the set {x}:
may be represented by the formal power series
The formal solution,
makes sense as a set of multisets, but the intermediate result, 1 − x, does not make sense as a set of multisets.
The infinite set of finite multisets of elements taken from the set represented by the monomial xy is
The infinite multiset of finite multisets of elements taken from the multiset represented by the monomial x2 may be taken as a special case where x = y:
The infinite multiset of finite multisets of elements taken from the multiset represented by the monomial xn is
This explains why "multisets are negative sets." The negative binomial coefficients count the number of k-multisets of elements taken from an n-set.
Cumulant generating function
A non-negative integer n, can be represented by the monomial xn. A finite multiset of non-negative integers can likewise be represented by a polynomial f(x).
It is convenient to consider the cumulant generating function g(t) = log f(et).
For example, the multiset {2, 2, 2, 3, 5} can be represented by the polynomial f(x) = 3x2 + x3 + x5, with cumulant generating function g(t) = log(3e2t + e3t + e5t), cardinality 3 + 1 + 1 = 5, derivative
The numbers
The infinite set of non-negative integers {0, 1, 2, ⋯} is represented by the formal power series 1 + x + x2 + ⋯ = (1 − x)−1. The mean value and standard deviation are undefined. Nevertheless, it has a cumulant-generating function, g(t) = −log(1 − et). The derivative of this cumulant-generating function is
A finite multiset of real numbers, A = {Ai}, is represented by the cumulant generating function
This representation is unique: different multisets have different cumulant generating functions. See partition function for the case where the numbers in question are the energy levels of a physical system.
The cumulant-generating function of a multiset of n real numbers having mean μ and standard deviation σ is g(t) = log n + μt + 2−1(σt)2 + ⋯ and the derivative is
The cumulant-generating function of a set {k} consisting of a single real number k is g(t) = kt. The derivative is the number itself:
The cumulant-generating function of a constant multiset, {k, k, k, k, ⋯, k} of n elements all equal to the same real number k, is g(t) = log n + kt, and the derivative is the number itself:
The cumulant-generating function of the multiset of sums of elements of two multisets of numbers is the sum of the two cumulant-generating functions:
There is no general formula for computing the cumulant generating function of a product
but the special case of a constant times a multiset of numbers is:
The multiset 2⋅A = {2Ai} is not the same multiset as 2 × A = A + A = {Ai + Aj}. For example,
The standard normal distribution is like a limit of large multisets of numbers.
This limit does not make sense as a multiset of numbers, but the derivative of the cumulant generating functions of the multisets in question makes sense, and the limit is well defined.
The constant term k2log(2) vanishes by differentiation. The terms ⋯ vanish in the limit. So for the standard normal distribution, having mean 0 and standard deviation 1, the derivative of the cumulant generating function is
Applications
Multisets have various applications. They are becoming the main structure of combinatorics because in its search for higher rigorousness, modern combinatorics has been developed not for sets but for multisets. Multisets have become an important tool in databases. For instance, multisets are often used to implement relations in database systems. Multisets also play an important role in computer science.
There are also other applications. For instance, Richard Rado used multisets as a device to investigate the properties of families of sets. He wrote, "The notion of a set takes no account of multiple occurrence of any one of its members, and yet it is just this kind of information which is frequently of importance. We need only think of the set of roots of a polynomial f(x) or the spectrum of a linear operator."
Generalizations
Different generalizations of multisets have been introduced, studied and applied to solving problems.