Multiset

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

In mathematics, a multiset (aka bag or mset) 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.

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:

• 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. The word "visa" is also used.

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

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

Formal definition

Axiomatic way

Basically there are two different ways appoaching to the multiset concept. Just like for sets, an axiomatic definition may be used, as it has been performed by Wayne Blizard 1989.. The complete list of multiset axioms will contain folowing subsections:

1. axioms for crispt sets (e. g. Zermelo–Fraenkel (ZFC).
2. axioms for the natural numbers (i. e. Peano axioms) - however the set of natural numbers may be constructed by (crisp) set theoretical means as given in item 1.
3. multiset specific axioms.

Constructive way

However, a more common way is the other one: Constructing multisets using a given set theory (e. g. ZFC), and a concept of natural numbers - no matter if axiomatic (Peano) or constructed by use of the set theory. According to this, a constructive definition will be given in the following.

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 integers. 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). Like any function, the function m may be defined as its graph, i. e. 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)}).

Given a universe U in which the elements of any set A must live, the definition can be simplified by extending the multiplicity to the whole universe. We then have a multiplicity function $m\colon U\to \mathbb {N} _{\geq 0}$ from U to the set $\mathbb {N} _{\geq 0}=\left\{0,1,2,3,\dots \right\}$ of nonnegative integers, obtained by extending m to U with values 0 for each element not in A.

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.

For normal sets the scenario is as follows: The set indicator function of a subset A of a set X is the function

$\mathbf {1} _{A}\colon 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 the set difference of sets is the zero-truncated subtraction of the indicator functions

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

The set indicator function of the symmetric difference of sets is the absolute of the difference of the indocator functions

$\mathbf {1} _{A\triangle B}(x)=|\mathbf {1} _{A}(x)-\mathbf {1} _{B}(x)|=max\{\mathbf {1} _{A}(x)-\mathbf {1} _{A}(x),\,\mathbf {1} _{B}(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)\leq \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 let us consider multisets: The concept of set indicator function is generalized by releasing the constraint that the values must be 0 and 1 only and allow values of 2, 3, 4 and so on. The resulting function is called a multiplicity function and such a function defines a multiset.

The support of a multiset $A$ in a universe $X$ is the set $\operatorname {Supp} (A)$ of elements of $X$ with non-zero multiplicity, that is:

$\operatorname {Supp} (A):=\left\{x\in X\mid \mathbf {1} _{A}(x)>0\right\}$.

Please note that index $A$ now denotes the multiset either given by axioms or by definition as above, rather than a crisp set. The normal set $A$ in the above notation now turns into the multiset's support $\operatorname {Supp} (A)$. $\mathbf {1} _{A}$ denotes the multiplicity function (as defined on the whole universe $U$).

The concepts of intersection, union, difference, symmetric difference, subset, cartesian product and cardinality of multisets are defined by the above formulas. Some of these definitions are very similar to those defined for fuzzy sets, e. g. support. Other parameters of multisets may be defined similar to those of fuzzy sets as well: relative cardiniality RelCard(A|G), height Hgt(A), and width Width(A). Further operations are as follows:

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

Example multiset operations

These examples demonstrate these operations of multiplicity functions.

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

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

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

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

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

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

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

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

Disjoint multisets

Two multisets $A,B$ are disjoint iff

$\forall$$x\in {X}:\mathbf {1} _{A}(x)=0\lor \mathbf {1} _{B}(x)=0$

which is equivalent to

$\nexists$ $u\in {U}:\mathbf {1} _{A}(u)>0\land \mathbf {1} _{B}(u)>0$

and also equivalent to

$\forall x\in {X}:min(\mathbf {1} _{A}(u),\mathbf {1} _{B}(u))=0$

Multisets are disjoint, iff their supports are disjoint according to the standard definition for sets.

For disjoint multisets $A,B$ intersection will give ∅ as well as well as scalar multiplication; and union will give the same result as multiset sum, which is denoted as

$A{\dot {\cup }}B=A\cup B=A\uplus B$

with its multiplicity function given by

$\forall x\in {X}:\mathbf {1} _{A{\dot {\cup }}{B}}(x)=max\{\mathbf {1} _{A}(x),\mathbf {1} _{B}(x)\}=\mathbf {1} _{A}(x)+\mathbf {1} _{B}(x)$

Note that only one of both summands may be greater than zero.

Example: Symmetric difference:

$A\triangle B=(A-B){\dot {\cup }}(B-A)$

For disjoint multisets $A,B$ the following holds true:

$Supp(A{\dot {\cup }}B)=Supp(A)\,{\dot {\cup }}\,Supp(B)$

The above can be generalized to finite families of multiets as follows: Given a family $A=(A_{i})_{i\in {I}}$ of multisets with Index set I (e.g. I = {1,2,3,...n}). This family is (pairwise) disjoint iff

$\forall x\in {X}\,\exists i\in {I}:\mathbf {1} _{A_{i}}(x)=0$

A family of multisets $A=(A_{i})_{i\in {I}}$ is disjoint, iff the family of underlying supports $Supp\circ A=(Supp(A_{i}))_{i\in {I}}$ is disjoint in the standard sense for families sets.

Independend of the t/s-norm pair, intersection of a disjoint family will give ∅ again as well as mutiplication (in case of finite index set I), while union and (finite) multiset sum give the same result:

${\dot {\bigcup \limits _{i\in {I}}}}A_{i}=\bigcup _{i\in {I}}A_{i}=\biguplus \limits _{i\in {I}}A_{i}$

with its multipicity function given by

$\forall x\in {X}:\mathbf {1} _{{\dot {\bigcup \limits _{i\in {I}}}}A_{i}}(u)=max\{\mathbf {1} _{A_{i}}(x)|i\in {I}\}=\sum _{i\in {I}}\mathbf {1} _{A_{i}}(x)$

Again only one of the summands is greater than zero.

For disjoint families of multisets $A=(A_{i})_{i\in {I}}$ the following holds true:

$Supp({\dot {\bigcup \limits _{i\in {I}}}}A_{i})={\dot {\bigcup \limits _{i\in {I}}}}Supp(A_{i})$

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 {n}{k}}$. 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 \choose 18}\!\!\right)={21 \choose 18}={\frac {21!}{18!\,3!}}={21 \choose 3}=\left(\!\!{19 \choose 3}\!\!\right),$

$={\frac {{\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}\cdot \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {red}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot 18}}}}},$

$={\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot 17\cdot 18\,\times \,\mathbf {1\cdot 2\cdot 3\quad } }},$

$={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.$

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 \mathbb {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).$

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

$\left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac {\alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\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 $\left(\!\!{\alpha \choose k}\!\!\right)$ negative binomial coefficients:

$(1-X)^{-\alpha }=\sum _{k=0}^{\infty }\left(\!\!{\alpha \choose 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

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

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^{tA_{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{aligned}g_{A+B}(t)&=\log \left(\sum _{i}\sum _{j}e^{t(A_{i}+B_{j})}\right)\\&=\log \left(\sum _{i}\sum _{j}e^{tA_{i}}e^{tB_{j}}\right)\\&=\log \left(\sum _{i}e^{tA_{i}}\cdot \sum _{j}e^{tB_{j}}\right)\\&=\log \left(\sum _{i}e^{tA_{i}}\right)+\log \left(\sum _{j}e^{tB_{j}}\right)\\&=g_{A}(t)+g_{B}(t).\end{aligned}}$

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^{tA_{i}B_{j}}\right),$

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

${\begin{aligned}g_{k\cdot A}(t)&=\log \left(\sum _{i}e^{t(kA_{i})}\right)\\&=\log \left(\sum _{i}e^{(tk)A_{i}}\right)\\&=g_{A}\left(kt\right).\end{aligned}}$

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)=kg_{A}(t).$

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

$\lim _{k\rightarrow \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{aligned}\lim _{k\rightarrow \infty }g'_{k^{-1}(k^{2}\times \{1,-1\})}(t)&=\lim _{k\rightarrow \infty }{\frac {d}{dt}}\left(k^{2}\log \left(e^{+tk^{-1}}+e^{-tk^{-1}}\right)\right)\\&=\lim _{k\rightarrow \infty }{\frac {d}{dt}}\left(k^{2}\log 2+2^{-1}t^{2}+\cdots \right)\\&=t.\end{aligned}}$

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 ^{2}t$.

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.

• Real-valued multisets (in which multiplicity of an element can be any real number)

This looks simple and straightforward as many definitions for fuzzy sets and multisets are very similar and can be taken over for real-valued multisets by just replacing the value range of the characteristic function ([0, 1] or ℕ₀ = {0, 1, 2, 3, ...} respectively) by ℝ₀⁺ = [0, ∞[. However this approach cannot be easily extended for genealized fuzzy sets where a poset or lattice is used instead of a simple degree of membership. Several other approachs for fuzzy multisets have been developped that don't show this restriction.

• Fuzzy multisets
• Rough multisets
• 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

• Frequency (statistics) as multiplicity analog
• Quasi-sets
• Set theory
• Partitions of multisets