Multiset

Examples

One of the simplest and most natural examples is the multiset of prime factors of a natural number n. Here the underlying set of elements is the set of prime factors of n. For example, the number 120 has the prime factorization $${\displaystyle 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. More generally, the fundamental theorem of algebra asserts that the complex solutions of a polynomial equation of degree d always form a multiset of cardinality d.

A special case of the above are the eigenvalues of a matrix, whose multiplicity is usually defined as their multiplicity as roots of the characteristic polynomial. However two other multiplicities are naturally defined for eigenvalues, their multiplicities as roots of the minimal polynomial, and the geometric multiplicity, which is defined as the dimension of the kernel of A − λI (where λ is an eigenvalue of the matrix A). These three multiplicities define three multisets of eigenvalues, which may be all different: Let A be a n × n matrix in Jordan normal form that has a single eigenvalue. Its multiplicity is n, its multiplicity as a root of the minimal polynomial is the size of the largest Jordan block, and its geometric multiplicity is the number of Jordan blocks.

Definition

A multiset may be formally defined as an ordered pair (U, m) where U is a set called a universe or the underlying set, and ${\displaystyle m:U\to \mathbb{N}}$ is a function from U to the nonnegative integers. The value ⁠${\displaystyle m(a)}$⁠ for an element ⁠${\displaystyle a\in U}$⁠ is called the multiplicity of ⁠${\displaystyle a}$⁠ in the multiset and interpreted as the number of occurrences of ⁠${\displaystyle a}$⁠ in the multiset.

The support, root, or carrier of a multiset is the subset of ⁠${\displaystyle U}$⁠ formed by the elements ⁠${\displaystyle a\in U}$⁠ such that ⁠${\displaystyle m(a)>0}$⁠. A finite multiset is a multiset with a finite support. Most authors define multisets as finite multisets. This is the case in this article, where, unless otherwise stated, all multisets are finite multisets.

Some authors define multisets with the additional constraint that ⁠${\displaystyle m(a)>0}$⁠ for every ⁠${\displaystyle a}$⁠, or, equivalently, the support equals the underlying set. Multisets with infinite multiplicities have also been studied; they are not considered in this article. Some authors define a multiset in terms of a finite index set ⁠${\displaystyle I}$⁠ and a function ⁠${\displaystyle f:I\to U}$⁠ where the multiplicity of an element ⁠${\displaystyle a\in U}$⁠ is ⁠${\displaystyle |f^{-1}(a)|}$⁠, the number of elements of ⁠${\displaystyle I}$⁠ that get mapped to ⁠${\displaystyle a}$⁠ by ⁠${\displaystyle f}$⁠.

Multisets may be represented as sets, with some elements repeated. For example, the multiset with support ⁠${\displaystyle \{a,b\}}$⁠ and multiplicity function such that ⁠${\displaystyle m(a)=2,m(b)=1}$⁠ can be represented as {a, a, b}. A more compact notation, in case of high multiplicities is ⁠${\displaystyle \{(a,2),(b,1)\}}$⁠ for the same multiset.

If ${\displaystyle A=\{a_1,\dots ,a_n\},}$ a multiset with support included in ⁠${\displaystyle A}$⁠ is often represented as $${\displaystyle a_1^{m(a_1)}\cdots a_n^{m(a_n)},}$$ to which the computation rules of indeterminates can be applied; that is, exponents 1 and factors with exponent 0 can be removed, and the multiset does not depend on the order of the factors. This allows extending the notation to infinite underlying sets as $${\displaystyle \prod _{a\in U}{a}^{m(a)}.}$$ An advantage of notation is that it allows using the notation without knowing the exact support. For example, the prime factors of a natural number ⁠${\displaystyle n}$⁠ form a multiset such that $${\displaystyle n=\prod _{p\text{prime}}{p}^{m(p)}=2^{m(2)}{3}^{m(3)}{5}^{m(5)}\cdots .}$$

Basic properties and operations

Elements of a multiset are generally taken in a fixed set U, sometimes called a universe, which is often the set of natural numbers. An element of U that does not belong to a given multiset is said to have a multiplicity 0 in this multiset. This extends the multiplicity function of the multiset to a function from U to the set ${\displaystyle \mathbb{N}}$ of non-negative integers. This defines a one-to-one correspondence between these functions and the multisets that have their elements in U.

This extended multiplicity function is commonly called simply the multiplicity function, and suffices for defining multisets when the universe containing the elements has been fixed. This multiplicity function is a generalization of the indicator function of a subset, and shares some properties with it.

The support of a multiset ${\displaystyle A}$ in a universe U is the underlying set of the multiset, which may be represented by ${\displaystyle A^{\ast }}$ or ${\displaystyle \mathrm{Supp}(A)}$. Using the multiplicity function ${\displaystyle m}$, it is characterized as $${\displaystyle \mathrm{Supp}(A):=\{x\in U\mid m_A(x)>0\}.}$$

A multiset is finite if its support is finite, or, equivalently, if its cardinality $${\displaystyle |A|=\sum _{x\in \mathrm{Supp}(A)}{m}_A(x)=\sum _{x\in U}{m}_A(x)}$$ is finite. The empty multiset is the unique multiset with an empty support (underlying set), and thus a cardinality 0.

The usual operations of sets may be extended to multisets by using the multiplicity function, in a similar way to using the indicator function for subsets. In the following, A and B are multisets in a given universe U, with multiplicity functions ${\displaystyle m_A}$ and ${\displaystyle m_B.}$

• Inclusion: A is included in B, denoted A ⊆ B, if $${\displaystyle m_A(x)\le m_B(x)\mathrm{\forall }x\in U.}$$
• Union: the union (called, in some contexts, the maximum or lowest common multiple) of A and B is the multiset C with multiplicity function $${\displaystyle m_C(x)=max(m_A(x),m_B(x))\mathrm{\forall }x\in U.}$$
• Intersection: the intersection (called, in some contexts, the infimum or greatest common divisor) of A and B is the multiset C with multiplicity function $${\displaystyle m_C(x)=min(m_A(x),m_B(x))\mathrm{\forall }x\in U.}$$
• Sum: the sum of A and B is the multiset C with multiplicity function $${\displaystyle m_C(x)=m_A(x)+m_B(x)\mathrm{\forall }x\in U.}$$ It may be viewed as a generalization of the disjoint union of sets. It defines a commutative monoid structure on the finite multisets in a given universe. This monoid is a free commutative monoid, with the universe as a basis.
• Difference: the difference of A and B is the multiset C with multiplicity function $${\displaystyle m_C(x)=max(m_A(x)-m_B(x),0)\mathrm{\forall }x\in U.}$$

Two multisets are disjoint if their supports are disjoint sets. This is equivalent to saying that their intersection is the empty multiset or that their sum equals their union.

There is an inclusion–exclusion principle for finite multisets (similar to the one for sets), stating that a finite union of finite multisets is the difference of two sums of multisets: in the first sum we consider all possible intersections of an odd number of the given multisets, while in the second sum we consider all possible intersections of an even number of the given multisets.

The finite subsets of a set ⁠${\displaystyle U}$⁠ are exactly the multisets with underlying set ⁠${\displaystyle U}$⁠, such that ⁠${\displaystyle m(a)\le 1}$⁠ for every ⁠${\displaystyle a\in U}$⁠.

Counting multisets

The number of multisets of cardinality k, with elements taken from a finite set of cardinality n, is sometimes called the multiset coefficient or multiset number. This number is written by some authors as ${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{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 ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k}).}$ Like the binomial distribution that involves binomial coefficients, there is a negative binomial distribution in which the multiset coefficients occur. Multiset coefficients should not be confused with the multinomial coefficients that occur in the multinomial theorem.

The value of multiset coefficients can be given explicitly as $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=(\genfrac{}{}{0ex}{}{n+k-1}{k})=\frac{(n+k-1)!}{k!(n-1)!}=\frac{n(n+1)(n+2)\cdots (n+k-1)}{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 of 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 $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=\frac{n^{\overline{k}}}{k!},}$$ to match the expression of binomial coefficients using a falling factorial power: $${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})=\frac{n^{\underset{\_}{k}}}{k!}.}$$

For example, there are ⁠${\displaystyle 4=\left((\genfrac{}{}{0ex}{}{2}{3})\right)}$⁠ multisets of cardinality 3 with elements taken from the two-elements set {1, 2}, namely {1, 1, 1}, {1, 1, 2}, {1, 2, 2}, and {2, 2, 2}. There are also ⁠${\displaystyle 4=(\genfrac{}{}{0ex}{}{4}{3})}$⁠ subsets of cardinality 3 in the four-element set {1, 2, 3, 4}, namely {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {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 of 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 $${\displaystyle (\genfrac{}{}{0ex}{}{4+18-1}{4-1})=(\genfrac{}{}{0ex}{}{4+18-1}{18})=1330,}$$ thus is the value of the multiset coefficient and its equivalencies: $${\displaystyle \begin{array}{cc}\left((\genfrac{}{}{0ex}{}{4}{18})\right)& =(\genfrac{}{}{0ex}{}{21}{18})=\frac{21!}{18!3!}=(\genfrac{}{}{0ex}{}{21}{3}),\\ & =\frac{\mathfrak{4}\cdot \mathfrak{5}\cdot \mathfrak{6}\cdot \mathfrak{7}\cdot \mathfrak{8}\cdot \mathfrak{9}\cdot \mathfrak{10}\cdot \mathfrak{11}\cdot \mathfrak{12}\cdot \mathfrak{13}\cdot \mathfrak{14}\cdot \mathfrak{15}\cdot \mathfrak{16}\cdot \mathfrak{17}\cdot \mathfrak{18}\cdot \mathbf{19}\cdot \mathbf{20}\cdot \mathbf{21}}{\mathbf{1}\cdot \mathbf{2}\cdot \mathbf{3}\cdot \mathfrak{4}\cdot \mathfrak{5}\cdot \mathfrak{6}\cdot \mathfrak{7}\cdot \mathfrak{8}\cdot \mathfrak{9}\cdot \mathfrak{10}\cdot \mathfrak{11}\cdot \mathfrak{12}\cdot \mathfrak{13}\cdot \mathfrak{14}\cdot \mathfrak{15}\cdot \mathfrak{16}\cdot \mathfrak{17}\cdot \mathfrak{18}},\\ & =\frac{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\cdot \mathbf{19}\cdot \mathbf{20}\cdot \mathbf{21}}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\cdot \mathbf{1}\cdot \mathbf{2}\cdot \mathbf{3}},\\ & =\frac{19\cdot 20\cdot 21}{1\cdot 2\cdot 3}.\end{array}}$$

From the relation between binomial coefficients and multiset coefficients, it follows that the number of multisets of cardinality k in a set of cardinality n can be written $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=(-1{)}^k(\genfrac{}{}{0ex}{}{-n}{k}).}$$ Additionally, $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=\left((\genfrac{}{}{0ex}{}{k+1}{n-1})\right).}$$

Recurrence relation

A recurrence relation for multiset coefficients may be given as $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=\left((\genfrac{}{}{0ex}{}{n}{k-1})\right)+\left((\genfrac{}{}{0ex}{}{n-1}{k})\right)\text{for }n,k>0}$$ with $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{0})\right)=1,n\in \mathbb{N},\text{and}\left((\genfrac{}{}{0ex}{}{0}{k})\right)=0,k>0.}$$

The above recurrence may be interpreted as follows. Let ${\displaystyle [n]:=\{1,\dots ,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 $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{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 $${\displaystyle \left((\genfrac{}{}{0ex}{}{n-1}{k})\right).}$$

Thus, $${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{k})\right)=\left((\genfrac{}{}{0ex}{}{n}{k-1})\right)+\left((\genfrac{}{}{0ex}{}{n-1}{k})\right).}$$

Generating series

The generating function of the multiset coefficients is very simple, being $${\displaystyle \sum _{d=0}^{\mathrm{\infty }}\left((\genfrac{}{}{0ex}{}{n}{d})\right)t^d=\frac{1}{(1-t{)}^n}.}$$ As multisets are in one-to-one correspondence with monomials, ${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{d})\right)}$ is also the number of monomials of degree d in n indeterminates. Thus, the above series is also the Hilbert series of the polynomial ring ${\displaystyle k[x_1,\dots ,x_n].}$

As ${\displaystyle \left((\genfrac{}{}{0ex}{}{n}{d})\right)}$ is a polynomial in n, it and the generating function are well defined for any complex value of n.

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, or complex): $${\displaystyle \left((\genfrac{}{}{0ex}{}{\alpha }{k})\right)=\frac{{\alpha }^{\overline{k}}}{k!}=\frac{\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}\text{for }k\in \mathbb{N}\text{ and arbitrary }\alpha .}$$

With this definition one has a generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the ${\displaystyle \left((\genfrac{}{}{0ex}{}{\alpha }{k})\right)}$ negative binomial coefficients: $${\displaystyle (1-X{)}^{-\alpha }=\sum _{k=0}^{\mathrm{\infty }}\left((\genfrac{}{}{0ex}{}{\alpha }{k})\right)X^k.}$$

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

$${\displaystyle (1-X{)}^{-\alpha }(1-X{)}^{-\beta }=(1-X{)}^{-(\alpha +\beta )}\text{and}((1-X{)}^{-\alpha }{)}^{-\beta }=(1-X{)}^{-(-\alpha \beta )},}$$ 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.

Applications

Multisets have various applications. They are becoming fundamental in combinatorics. Multisets have become an important tool in the theory of relational databases, which often uses the synonym bag. For instance, multisets are often used to implement relations in database systems. In particular, a table (without a primary key) works as a multiset, because it can have multiple identical records. Similarly, SQL operates on multisets and returns identical records. For instance, consider "SELECT name FROM Student". In the case that there are multiple records with name "Sara" in the student table, all of them are shown. That means the result of an SQL query is a multiset; if the result were instead a set, the repetitive records in the result set would have been eliminated. Another application of multisets is in modeling multigraphs. In multigraphs there can be multiple edges between any two given vertices. As such, the entity that specifies the edges is a multiset, and not a set.

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 that 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.

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