Multiset

This article is about the mathematical concept. For the computer science data structure, see Multiset (abstract data type).

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. 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 elements a and b, varying only by multiplicity:

• The unique set {a, b} contains only elements a and b, each having multiplicity 1
• In multiset {a, a, b}, a has multiplicity 2 and b has multiplicity 1
• In multiset {a, a, a, b, b, b}, a and b both have multiplicity 3

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. However, mathematicians formalized multisets and began to study them as a precise mathematical object (structure) only in the 20th century.

Formal definition

Within set theory, a multiset may be formally defined as a 2-tuple (A, m) where A is some set and $m \colon A \to \mathbb{N}_{\geq 1}$ is a function from A to the set $\mathbb{N}_{\geq 1} = \left\{1, 2, 3, \dots\right\}$ of positive natural numbers. The set A is called the underlying set of elements. For each a in A the multiplicity (that is, number of occurrences) of a is the number m(a). If a universe U in which the elements of A must live is specified, the definition can be simplified to just a multiplicity function $m_U\colon U \to \mathbb{N}$ from U to the set $\mathbb{N} = \left\{0, 1, 2, 3, \dots\right\}$ of natural numbers, obtained by extending m to U with values 0 for each element not in A. This extended multiplicity function is the multiplicity function called 1_A below. Like any function, the function m may be defined as its graph: the set of ordered pairs $\left\{\left(a, m\left(a\right)\right) : a \in A\right\}$. With these definitions the multiset written as {a, a, b} is defined as ({a, b}, {(a, 2), (b, 1)}), and the multiset {a, b} is defined as ({a, b}, {(a, 1), (b, 1)}).

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, (a_i), where i is in some index-set, may define a multiset, sometimes written {a_i}, in which the multiplicity of any element x is the number of indices i such that $a_i = x$. The condition for this to be possible is that no element occurs infinitely many times in the family: even in an infinite multiset, the multiplicities must be finite numbers.

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

$\mathbf{1}_A : X \to \lbrace 0,1 \rbrace \,$

defined by

$\mathbf{1}_A(x) = \begin{cases} 1 &\text{if }x \in A, \\ 0 &\text{if }x \notin A. \end{cases}$

The set indicator function of the intersection of sets is the minimum function of the indicator functions

$\mathbf{1}_{A\cap B}(x) = \min\{\mathbf{1}_A(x),\mathbf{1}_B(x)\}.$

The set indicator function of the union of sets is the maximum function of the indicator functions

$\mathbf{1}_{A\cup B}(x) = \max\{{\mathbf{1}_A(x),\mathbf{1}_B(x)}\}.$

The set indicator function of a subset is smaller than or equal to that of the superset

$A\subseteq B \Leftrightarrow \forall x \mathbf{1}_{A}(x) \le \mathbf{1}_{B}(x).$

The set indicator function of a cartesian product is the product of the indicator functions of the cartesian factors

$\mathbf{1}_{A \times B}(x,y) = \mathbf{1}_A(x) \cdot\mathbf{1}_B(y).$

The cardinality of a (finite) set is the sum of the indicator function values

$|A|=\sum_{x\in X} \mathbf{1}_{A}(x).$

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, subset, cartesian product and cardinality of multisets are defined by the above formulas.

The multiplicity function of a multiset sum, is the sum of the multiplicity functions

$\mathbf{1}_{A \uplus B}(x) = \mathbf{1}_A(x) + \mathbf{1}_B(x).$

The multiplicity function of a multiset difference is the zero-truncated subtraction of the multiplicity functions

$\mathbf{1}_{A \setminus B}(x) = \max(0, \mathbf{1}_A(x) - \mathbf{1}_B(x)).$

The scalar multiplication of a multiset by a natural number n may be defined as:

$\mathbf{1}_{n \otimes A}(x) = n \times \mathbf{1}_A(x). \,$

A small finite multiset, A, is represented by a list where each element, x, occurs as many times as the multiplicity, 1_A(x), indicates.

$\{1,1,1,3\} \cap \{1,1,2\} = \{1,1\} \,$

$\{1,1\} \cup \{1,2\} = \{1,1,2\}\,$

$\{1,1\} \subseteq \{1,1,1,2\}\,$

$\left|\{1,1\}\right|=2 \,$

$\{1,1\} \times \{1,2\} = \{(1,1), (1,1), (1,2), (1,2)\} \,$

$\{1,1\} \uplus \{1,2\} = \{1,1,1,2\} \,$

Examples

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

$120 = 2^3 3^1 5^1\,$

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.

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

Bijection between 3-subsets of a 7-set (left)
and 3-multisets with elements from a 5-set (right)
So this illustrates that $\textstyle {7 \choose 3} = \left(\!\!{5 \choose 3}\!\!\right)$.

See also: Stars and bars (combinatorics)

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 $\textstyle\left(\!\!{n\choose k}\!\!\right)$, a notation that is meant to resemble that of binomial coefficients; it is used for instance in (Stanley, 1997), and could be pronounced "n multichoose k" to resemble "n choose k" for $\tbinom nk$. Unlike for binomial coefficients, there is no "multiset theorem" in which multiset coefficients would occur, and they should not be confused with the unrelated multinomial coefficients that occur in the multinomial theorem.

The value of multiset coefficients can be given explicitly as

$\left(\!\!{n\choose k}\!\!\right) = {n+k-1 \choose k} = \frac{(n+k-1)!}{k!\,(n-1)!} = {n(n+1)(n+2)\cdots(n+k-1)\over k!},$

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

$\left(\!\!{n\choose k}\!\!\right) = {n^{\overline{k}}\over k!},$

to match the expression of binomial coefficients using a falling factorial power:

${n\choose k} = {n^{\underline{k}}\over k!}.$

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:

$\bullet \bullet \bullet \bullet \bullet \bullet \mid \bullet \bullet \mid \bullet \bullet \bullet \mid \bullet \bullet \bullet \bullet \bullet \bullet \bullet$

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

${4+18-1 \choose 4-1}={4+18-1 \choose 18} = 1330,$

thus is the value of the multiset coefficient and its equivalencies:

$\left(\!\!{4\choose18}\!\!\right)={21\choose18}=\frac{21!}{18!\,3!}={21\choose3}=\left(\!\!{19\choose3}\!\!\right),$

$=\frac{{\color{Purple}{\mathfrak{ 4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}} \mathbf{\cdot19\cdot20\cdot21}}{\mathbf{1\cdot2\cdot3}{\color{Purple}{\mathfrak{\cdot 4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}},$

$=\frac{ 1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18\;\mathbf{\cdot\;19\cdot20\cdot21}} {\,1\cdot2\cdot3\cdot4\cdot5\cdots 16\cdot17\cdot18\,\times\,\mathbf{1\cdot2\cdot3\quad}},$

$=\frac{19\cdot20\cdot21}{1\cdot2\cdot3}.$

One may define a generalized binomial coefficient

${n \choose k}={n(n-1)(n-2)\cdots(n-k+1) \over k!}$

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

$\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k}.$

Recurrence relation

A recurrence relation for multiset coefficients may be given as

$\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right) \quad \mbox{for } n,k>0$

with

$\left(\!\!{n \choose 0}\!\!\right) = 1,\quad n\in\N, \quad\mbox{and}\quad \left(\!\!{0 \choose k}\!\!\right) = 0,\quad k>0.$

The above recurrence may be interpreted as follows. Let [n] := $\{1,\cdots,n\}$ be the source set. There is always exactly one (empty) multiset of size 0, and if n = 0 there are no larger multisets, which gives the initial conditions.

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

$\left(\!\!{n\choose k - 1}\!\!\right)$ possibilities.

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

$\left(\!\!{n-1\choose k}\!\!\right).$

Thus,

$\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right).$

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

$(1 + x)(1 + y) = 1 + x + y + xy.$

The multiset {x, x} may be represented by the monomial x². The multiset of submultisets of {x, x}, {{}, {x}, {x}, {x, x}}, is represented by the polynomial

$(1 + x)^2 = 1 + 2x + x^2.$

The multiset of submultisets of the multiset represented by the polynomial xⁿ is

$(1+x)^n=\sum_{k=0}^n{n \choose k} x^k.$

That is why the binomial coefficient counts the number of k-combinations of an n-set.

The multiset represented by the polynomial x^Ky^{N − 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

$(1 + x)^K(1 + y)^{N-K}$

which by the binomial theorem equals

$\sum_{n=0}^N\sum_{k=0}^K{K \choose k}{N-K \choose n-k} x^k y^{n-k}.$

So the number of n-samples with k hits is

${K \choose k}{N-K \choose n-k}.$

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}:

$\{ \{\}, \{x\}, \{x,x\}, \{x,x,x\}, \cdots \}$

may be represented by the formal power series

$S=1+x+x^2+x^3+\cdots=1+xS.$

The formal solution,

$S=(1-x)^{-1},$

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

$(1-x)^{-1}(1-y)^{-1}=1+(x+y)+(x^2+xy+y^2)+\cdots.$

The infinite multiset of finite multisets of elements taken from the multiset represented by the monomial x² may be taken as a special case where x = y:

$(1-x)^{-2}=1+2x+3x^2+\cdots.$

The infinite multiset of finite multisets of elements taken from the multiset represented by the monomial xⁿ is

$(1-x)^{-n}=\sum_{k=0}^\infty{-n \choose k} (-x)^k.$

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 xⁿ. 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(e^t).

• The cardinality of the multiset is e^g(0) = f(1).
• The derivative of the cumulant generating function is $g'(t) = f(e^t)^{-1} f'(e^t) e^t$.
  • The mean value of the multiset is $\mu=g'(0)= f(1)^{-1}f'(1)$.
  • The variance of the multiset is $\sigma^2=g''(0)$.

For example, the multiset {2, 2, 2, 3, 5} can be represented by the polynomial f(x) = 3x² + x³ + x⁵, with cumulant generating function g(t) = log(3e^2t + e^3t + e^5t), cardinality 3 + 1 + 1 = 5, derivative $g'(t) = (3e^{2t}+e^{3t}+e^{5t})^{-1}(6e^{2t}+3e^{3t}+5e^{5t})$, and mean value μ = (3 + 1 + 1)⁻¹(6 + 3 + 5) = 2.8.

The numbers $(\mu,\sigma^2,\cdots)=(g'(0),g''(0),\cdots)$ are called cumulants.

The infinite set of non-negative integers {0, 1, 2, ⋯} is represented by the formal power series 1 + x + x² + ⋯ = (1 − x)⁻¹. The mean value and standard deviation are undefined. Nevertheless, it has a cumulant-generating function, g(t) = −log(1 − e^t). The derivative of this cumulant-generating function is $g'(t)=(e^{-t}-1)^{-1}$.

A finite multiset of real numbers, A = {A_i}, is represented by the cumulant generating function

$g_A(t) = \log \left(\sum_i e^{t A_i}\right).$

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⁻¹(σt)² + ⋯ and the derivative is $g'(t)=\mu+\sigma^2 t+\cdots$.

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: $g'(t)=k$. So the concept of the derivative of the cumulant generating function of a multiset of real numbers is a generalization of the concept of a real number.

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: $g'(t)=k$, irrespective of n.

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:

$\begin{align} g_{A+B}(t) &= \log \left(\sum_i \sum_j e^{t(A_i+B_j)}\right) \\ &= \log \left(\sum_i\sum_j e^{t A_i} e^{t B_j}\right) \\ &= \log \left(\sum_i e^{t A_i}\cdot \sum_j e^{t B_j}\right) \\ &= \log \left(\sum_i e^{t A_i}\right)+ \log\left(\sum_j e^{t B_j}\right) \\ &= g_A(t) + g_B(t). \end{align}$

There is no general formula for computing the cumulant generating function of a product

$g_{A\cdot B}(t) = \log \left(\sum_i\sum_j e^{t A_i B_j}\right),$

but the special case of a constant times a multiset of numbers is:

$\begin{align} g_{k\cdot A}(t) &= \log \left(\sum_i e^{t (kA_i)}\right) \\ &= \log \left(\sum_i e^{(t k) A_i}\right) \\ &= g_A\left(k t\right). \end{align}$

The multiset 2⋅A = {2A_i} is not the same multiset as 2 × A = A + A = {A_i + A_j}. For example, $2 \cdot\{1,-1\} = \{2,-2\}$ while 2 × {1, −1} = {1, −1} + {1, −1} = {1 + 1, 1 − 1, −1 + 1, −1 −1} = {2, 0, 0, −2}. The cumulant generating function of k × A is

$g_{k\times A}(t) = k g_{A}(t).$

The standard normal distribution is like a limit of large multisets of numbers.

$\lim_{k \rarr \infty}k^{-1} \left(k^2\times \{1,-1\}\right).$

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.

$\begin{align} \lim_{k \rarr \infty} g'_{k^{-1} (k^2\times \{1,-1\})}(t) & = \lim_{k \rarr \infty} \frac{d}{dt}\left(k^2 \log\left(e^{+t k^{-1}}+e^{-t k^{-1}}\right)\right) \\ & = \lim_{k \rarr \infty} \frac{d}{dt}\left(k^2 \log 2+2^{-1} t^2+\cdots\right) \\ & = t. \end{align}$

The constant term k²log(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 $g'(t)=t$. For the normal distribution having mean μ and standard deviation σ, the derivative of the cumulant generating function is $g'(t)=\mu+\sigma^2t$.

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.

• Fuzzy multisets
• Rough multisets
• Real-valued multisets (in which multiplicity of an element can be any real number)
• Hybrid sets
• where multiplicity is any real-valued step function
• Soft multisets
• Soft fuzzy multisets
• Named set (unification of all generalizations of sets)

See also

• Set Theory