Multiset

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

In mathematics, the notion of multiset (or bag) is a generalization of the notion of set in which members are allowed to appear more than once. For example, there is a unique set that contains the elements a and b and no others, but there are many multisets with this property, such as the multiset that contains two copies of a and one of b or the multiset that contains three copies of both a and b. The term "multiset" was coined by Nicolaas Govert de Bruijn in the 1970s.^[1] The use of multisets in mathematics predates the name "multiset" by nearly 90 years: Richard Dedekind used multisets in a paper published in 1888.^[2]

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 brackets is sometimes used: the multiset {2,2,3} can be represented as [2,2,3].^[3] In multisets, as in sets and in contrast to tuples, the order of elements is irrelevant: The multisets {a, b} and {b, a} are equal.

Formal definition

Within set theory, a multiset may be formally defined as a 2-tuple(A, m) where A is some set and m : A → N_≥1 is a function from A to the set N_≥1 = {1, 2, 3, ...} 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 : U → N from U to the set N = {0, 1, 2, 3, ...} of natural numbers, obtained by extending m to U with values 0 outside 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 { (a, m(a)) : a in A }. 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). However to replace set theory by "multiset theory" so as to have multisets directly into the foundations is not easy: a privileged role would still have to be given to (ordinary) sets when defining maps, as there is no clear notion of maps (functions) between multisets. It can be done^{[not specific enough to verify]}, with the result that classical theorems such as the Cantor–Bernstein–Schroeder theorem or Cantor's theorem, when generalized to multisets, are false^{[examples needed]}; they remain true only in the case of finite multisets^{[citation needed]}. In addition, the notion of a set as a "class of items satisfying a certain property" – i.e. the extension of a predicate – is used throughout mathematics, and this notion lacks a sensible generalization to multisets with multiple memberships.

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.

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.

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

See also: Stars and bars (probability)

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(n+1)(n+2)\cdots(n+k-1)\over k!} = {n + k - 1 \choose k},$

where the last expression expresses it as 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}. And there are also 4 subsets of cardinality 3 in the set {1,2,3,4} of cardinality 4 (n+k-1 = 4), 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 18 made of elements of a set of cardinality 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

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

so that is the value of the multiset coefficient

$\left(\!\!{4\choose18}\!\!\right).$

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}.$

This fact led Gian-Carlo Rota to ask "Why are negative sets multisets?".^{[citation needed]} He considered that question worthy of the attention of philosophers of mathematics.

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, ..., 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. The set of subsets, { {}, {x} } , is represented by the binomial 1 + x.

The set {x,y} may be represented by the monomial x·y. The set of subsets, { {}, {x}, {y}, {x,y} } , is represented by the polynomial

(1 + x)·(1 + y) = 1 + x + y + x·y.

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

(1 + x)² = 1 + x + x + x·x = 1 + 2·x + x².

The multiset of submultisets of the multiset xⁿ is

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

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

The multiset x^K·y^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}\cdot{N-K \choose n-k}\cdot x^k\cdot y^{n-k}.$

So the number of n-samples with k hits is

${K \choose k}\cdot{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}, ... }

may be represented by the formal power series

S = 1 + x + x² + x³ + ... = 1 + xS .

The formal solution,

S = (1 − x)⁻¹,

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 x·y is

(1 − x)⁻¹·(1 − y)⁻¹ = 1 + (x + y) + (x² + x·y + y²) + ...

The special case y=x : The infinite multiset of finite multisets of elements taken from the multiset x² is

(1 − x)⁻² =  1 + 2·x + 3·x² + ...

The general case: The infinite multiset of finite multisets of elements taken from the multiset xⁿ is

$(1-x)^{-n}=\sum_{k=0}^\infty{-n \choose k} \cdot(-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, say {2, 2, 2, 3, 5}, can likewise be represented by a polynomial f(x), say f(x) = 3·x² + x³ + x⁵ .

It is convenient to consider the cumulant generating function g(t) = log(f(e^t)), say g(t) = log(3·e^2·t + e^3·t  + e^5·t) .

• The cardinality of the multiset is e^g(0) = f(1), say 3 + 1 + 1 = 5.

• The derivative g is g '(t) = f(e^t)⁻¹·f '(e^t)·e^t, say g '(t) = (3·e^2·t + e^3·t + e^5·t)⁻¹·(6·e^2·t + 3·e^3·t + 5·e^5·t) .
  • The mean value of the multiset is μ = g '(0) = f(1)⁻¹·f '(1), say μ = (3+1+1)⁻¹·(6+3+5) = 2.8 .
  • The variance of the multiset is σ² = g ' '(0) .

The numbers ( μ, σ², ··· )  = ( g '(0), g ' '(0), ··· ) 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)⁻¹.

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 \cdot A_i}\right) .$

This representation is unique: different multisets have different cumulant generating functions. See partition function (statistical mechanics) 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 simply: g '(t) = μ + σ²·t + ···

The cumulant-generating function of set, {k}, consisting of a single real number, k, is g(t) = k·t , and 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)+k·t , 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\cdot(A_i+B_j)}\right) = \log \left(\sum_i\sum_j e^{t\cdot A_i}\cdot e^{t\cdot B_j}\right) \\ & = \log \left(\sum_i e^{t\cdot A_i}\cdot \sum_j e^{t\cdot B_j}\right) = \log \left(\sum_i e^{t\cdot A_i}\right)+ \log\left(\sum_j e^{t\cdot B_j}\right) \\ & = g_A(t) + g_B(t). \end{align}$

There is unfortunately 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\cdot A_i\cdot B_j}\right) \,$

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

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

The multiset 2·A = {2·A_i} is not the same multiset as 2×A =A+A = {A_i+A_j}. For example, 2·{+1,−1} = {+2,−2} while 2×{+1,−1} = {+1,−1} + {+1,−1} = {+1+1,+1−1,−1+1,−1−1} = {+2,0,0,−2}.

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

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

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

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}\cdot (k^2\times \{+1,-1\})}(t) & = \lim_{k \rarr \infty} \frac{d(k^2\cdot \log(e^{+t\cdot k^{-1}}+e^{-t\cdot k^{-1}}))}{dt} \\ & = \lim_{k \rarr \infty} \frac{d(k^2\cdot \log(2)+2^{-1}\cdot t^2+\cdots)}{dt}=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 simply g '(t) = t . For the normal distribution having mean μ and standard deviation σ, the derivative of the cumulant generating function is g '(t) = μ + σ²·t .

See also random variable.

Notes

1. ^ Knuth, Donald E. (1998). The Art of Computer Programming – Vol. 2: Seminumerical Algorithms (3rd edition ed.). Addison Wesley. pp. 694. ISBN 0201896842.  Knuth also lists other names that were proposed for multisets, such as list, bunch, bag, heap, sample, weighted set, collection, and suite.
2. ^ Syropoulos, Apostolos (2001), p. 347
3. ^ Hein, James L. (2003). Discrete mathematics. Jones & Bartlett Publishers. pp. 29–30. ISBN 0763722103. 

References

• Blizard, Wayne D. (1989) "Multiset theory," Notre Dame Journal of Formal Logic, Volume 30, Number 1, Winter: pp. 36–66. doi:10.1305/ndjfl/1093634995 http://projecteuclid.org/euclid.ndjfl/1093634995 MR990203 0668.03027
• Bogart, Kenneth P. (2000). Introductory combinatorics, 3rd. ed. San Diego CA: Harcourt.
• Gessel, Ira M., and Stanley, Richard P. (1995) "Algebraic enumeration" in Graham, R. L., Grötschel, M., & Lovász, L., eds., Handbook of combinatorics, Vol. 2. Elsevier: 1021–1061. ISBN 0-444-82351-4, 0-444-88002-X, 0-262-07171-1, 0-262-07169-X.

Multisets are discussed on pp. 1036–1039.

• Hickman, J. L. (1980) "A note on the concept of multiset," Bulletin of the Australian Mathematical Society 22: 211–17.
• Stanley, Richard P. (1997, 1999) Enumerative Combinatorics, Vols. 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, 0-521-56069-1.
• Syropoulos, Apostolos (2001) "Mathematics of Multisets" in C. S. Calude et al., eds., Multiset processing: Mathematical, computer science, and molecular computing points of view, LNCS 2235. Springer-Verlag: 347–358.