# Multiset

{{#invoke:Hatnote|hatnote}}

In mathematics, the notion of **multiset** (or **bag**) is a generalization of the notion of a set in which members are allowed to appear more than once. For example, there is a unique set {*a*, *b*} containing elements *a* and *b* and no others, but there are many multisets containing *a* and *b* (and no others) with various multiplicities. For instance, in the multiset {*a*, *a*, *b*}, *a* has multiplicity 2 and *b* has multiplicity 1; and in the multiset {*a*, *a*, *a*, *b*, *b*, *b*}, *a* and *b* each have multiplicity 3. The term "multiset" was coined by Nicolaas Govert de Bruijn in the 1970s.^{[1]}
The use of multisets in mathematics and beyond predates the name "multiset" by many centuries: Knuth (1998) attributes the first study of multisets to the Indian mathematician Bhāskarāchārya (circa 1150), who described permutations of multisets.

## 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].^{[2]} 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

Blizard (1989) 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 (Blizard, 1991). For instance, they are called bags by Peterson (1981), who attributed this term to Cerf, Gostelow, Estrin, and Volanski (1971). A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set) (cf. (Blizard, 1991; Singh, et al., 2007)).

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 Bhascara Acharya (circa 1150), who described permutations of multisets (Knuth, 1998). Angelelli (1965) discovered another early reference to the concept of multiset in the work of Marius Nizolius (1498-1576). Much later Kircher (1650) found the number of multiset permutations when one element can be repeated. Prestet (1675) published a general rule for multiset permutations. Wallis (1685) explains this rule in more detail.

In the explicit form, multisets appeared in the work of Richard Dedekind "*Was sind und was sollen die Zahlen?*" (1888). 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 where is some set and is a function from to the set of positive natural numbers. The set is called the *underlying set of elements*. For each in the *multiplicity* (that is, number of occurrences) of is the number . If a universe in which the elements of must live is specified, the definition can be simplified to just a multiplicity function from to the set of natural numbers, obtained by extending to with values 0 for each element not in . This extended multiplicity function is the multiplicity function called below. Like any function, the function may be defined as its graph: the set of ordered pairs . With these definitions the multiset written as is defined as , and the multiset is defined as .

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, , where is in some index-set, may define a multiset, sometimes written , in which the multiplicity of any element is the number of indices such that . 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

defined by

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

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

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

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

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

Now generalize the concept of set indicator function by releasing the constraint that the values are 0 and 1 only and allow the values 2, 3, 4 and so on. The resulting function is called a **multiplicity function** and such a function defines a **multiset**. The concepts of intersection, union, 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

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

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

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.

## 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

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

{{#invoke:see also|seealso}}
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 , 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 . 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

where the second expression is as a binomial coefficient; many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality *k* in a set of cardinality *n* + *k* − 1. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a rising factorial power

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

There are for example 4 **multisets** of cardinality 3 with elements taken from the set {1,2} of cardinality 2 (*n*=2, *k*=3), namely : {1,1,1}, {1,1,2}, {1,2,2}, {2,2,2}. 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 *a*s, 2 *b*s, 3 *c*s, 7 *d*s) in this form:

This is a multiset of cardinality k=18 made of elements of a set of cardinality n=4. The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1. The number of vertical lines is 4 − 1. The number of multisets of cardinality 18 is then the number of ways to arrange the 4 − 1 vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 in a set of cardinality 18 + 4 − 1. Equivalently, it is the number of ways to arrange the 18 dots among the 18 + 4 − 1 characters, which is the number of subsets of cardinality 18 of a set of cardinality 18 + 4 − 1. This is

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

One may define a generalized binomial coefficient

in which *n* is not required to be a nonnegative integer, but may be negative or a non-integer, or a non-real complex number. (If *k* = 0, then the value of this coefficient is 1 because it is the empty product.) Then the number of multisets of cardinality *k* in a set of cardinality *n* is

### Recurrence relation

A recurrence relation for multiset coefficients may be given as

with

The above recurrence may be interpreted as follows.
Let [*n*] := {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

If *n* does not appear, then our original multiset is equal to a multiset of cardinality *k* with elements from [*n* − 1], of which there are

Thus,

## 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*^{2}. The multiset of submultisets, { {}, {*x*}, {*x*}, {*x,x*} }, is represented by the polynomial

- (1 +
*x*)^{2}= 1 +*x*+*x*+*x·x*= 1 + 2·*x*+*x*^{2}.

The multiset of submultisets of the multiset *x*^{n} is

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

So the number of *n*-samples with *k* hits is

See hypergeometric distribution and inferential statistics for further on the distribution of hits.

The infinite set of finite multisets of elements taken from the set {*x*}:

- { {}, {
*x*}, {*x*,*x*}, {*x*,*x*,*x*}, ... }

may be represented by the formal power series

*S*= 1 +*x*+*x*^{2}+*x*^{3}+ ... = 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 *x·y* is

- (1 −
*x*)^{−1}·(1 −*y*)^{−1}= 1 + (*x*+*y*) + (*x*^{2}+*x·y*+*y*^{2}) + ...

The special case *y*=*x* : The infinite multiset of finite multisets of elements taken from the multiset *x*^{2} is

- (1 −
*x*)^{−2}= 1 + 2·*x*+ 3·*x*^{2}+ ...

The general case:
The infinite multiset of finite multisets of elements taken from the multiset *x*^{n} is

This explains why "multisets are negative sets". The negative binomial coefficients count the number of *k*-multisets of elements taken from an *n*-set.

## Cumulant generating function

A non-negative integer, *n*, can be represented by the monomial *x*^{n} . 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*^{2} + *x*^{3} + *x*^{5} .

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})^{−1}·*f*'(e^{t})·e^{t}, say*g*'(*t*) = (3·e^{2·t}+ e^{3·t}+ e^{5·t})^{−1}·(6·e^{2·t}+ 3·e^{3·t}+ 5·e^{5·t}) .- The mean value of the multiset is μ =
*g*'(0) =*f*(1)^{−1}·*f*'(1), say μ = (3+1+1)^{−1}·(6+3+5) = 2.8 . - The variance of the multiset is σ
^{2}=*g*' '(0) .

- The mean value of the multiset is μ =

The numbers ( μ, σ^{2}, ··· )
= ( *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*^{2} + ··· = (1 − *x*)^{−1}. 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

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^{−1}·(σ·*t*)^{2} + ··· ,
and the derivative is simply: *g* '(*t*) = μ + σ^{2}·*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:

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

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

The multiset 2·*A* = {2·*A _{i}*} is not the same multiset as 2×

*A*=

*A*+

*A*= {

*A*+

_{i}*A*}. 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}.

_{j}The standard normal distribution is like a limit of big multisets of numbers.

This limit does not make sense as a multiset of numbers, but the derivative of the cumulant generating functions of the multisets in question makes sense, and the limit is well defined.

The constant term *k*^{2}·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*) = μ + σ^{2}·*t* .

See also random variable.

## Applications

Multisets have various applications (Singh, et al., 2007). 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 (Aigner, 1979; Anderson, 1987; Stanley, 1999). Multisets have become an important tool in databases (Libkin and Wong, 1994; 1995; Grumbach and Milo, 1996). For instance, multisets are often used to implement relations in database systems. Multisets also play an important role in computer science (Knuth, 1997; 1998).

There are also other applications. For instance, Rado (1975) uses multisets as a device to investigate the properties of families of sets. He writes, "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.

Yager (1986) introduced fuzzy multisets under the name fuzzy bags.

Grzymala-Busse (1987) introduced the concept of a rough multiset, using multirelations.

Blizard (1989) generalized multisets to real valued multisets, i.e., multisets in which multiplicity of an element can be any non-negative real number. Blizard (1990) also introduced multisets with negative multiplicity.

Loeb (1992) introduced hybrid sets as a generalization of multisets in which multiplicity of an element is any integer number.

Miyamoto (2001) further generalized multisets introducing multisets in which multiplicity of an element is any real-valued step function.

Alkhazaleh, Salleh and Hassan (2011) introduced soft multisets, while Alkhazaleh and Salleh (2012) introduced fuzzy soft multisets.

Burgin (1990; 1992; 2004; 2011) unified multisets and all their generalizations by the concept of a named set, which also comprises all other generalizations of sets.

## Notes

## References

- Aigner, M. (1979).
*Combinatorial Theory*, Springer Verlag, New York/Berlin. - Alkhazaleh, S. and Salleh, A.R. (2012). Fuzzy Soft Multiset Theory,
*Abstract and Applied Analysis*, article ID 350600, 20 p. - Alkhazaleh, S., Salleh, A.R. and Hassan, N. (2011). Soft Multisets Theory,
*Applied Mathematical Sciences*, 5(72):3561–3573. - Anderson, I. (1987).
*Combinatorics of Finite Sets*, Clarendon Press, Oxford. - Angelelli, I. (1965). Leibniz's misunderstanding of Nizolius' notion of 'multitudo', Notre Dame Journal of Formal Logic, 6:319–322.
- Blizard, Wayne D. (1989). "Multiset theory,"
*Notre Dame Journal of Formal Logic*, 30(1), Winter:36–66. Template:Hide in printTemplate:Only in print http://projecteuclid.org/euclid.ndjfl/1093634995 MR990203 0668.03027 - Blizard, WD. (1989). Real-valued Multisets and Fuzzy Sets,
*Fuzzy Sets and Systems*, 33:77–97. - Blizard, W. (1990). Negative Membership,
*Notre Dame Journal of Formal Logic*, 31(1):346–368. - Blizard, WD. (1991). The Development of Multiset Theory,
*Modern Logic*, 1(4):319–352. - Bogart, Kenneth P. (2000).
*Introductory combinatorics*, 3rd. ed. San Diego CA: Harcourt. - Burgin M. (1990). Theory of Named Sets as a Foundational Basis for Mathematics, In:
*Structures in Mathematical Theories*, San Sebastian, pp. 417–420 (http://www.blogg.org/blog-30140-date-2005-10-26.html) - Burgin, M. (1992). On the concept of a multiset in cybernetics,
*Cybernetics and System Analysis*, 3:165–167. - Burgin, M. (2004). Unified Foundations of Mathematics, Preprint Mathematics LO/0403186, 39 p. (electronic edition: http://arXiv.org)
- Burgin, M. (2011), Theory of Named Sets,
*Mathematics Research Developments*, Nova Science Pub Inc, ISBN 978-1-61122-788-8, books.google.com - Dedekind R. (1888).
*Was sind und was sollen die Zahlen?*, Vieweg, Braunschweig. - Gessel, Ira M., and Stanley, Richard P. (1995). "Algebraic enumeration" in Graham, R. L., Grötschel, M., & Lovász, L., eds.,
*Handbook of combinatorics*, 2:1021–1061. Elsevier, ISBN 0-444-82351-4, 0-444-88002-X, 0-262-07171-1, 0-262-07169-X. - Grzymala-Busse, J. (1987). Learning from examples based on rough multisets, in
*Proceedings of the 2nd International Symposium on Methodologies for Intelligent Systems*, Charlotte, NC, USA, pp. 325–332. - Grumbach, S. and Milo, T. (1996). Towards tractable algebras for bags,
*Journal of Computer and System Sciences*, 52(3):570–588. - Hickman, J. L. (1980). A note on the concept of multiset,
*Bulletin of the Australian Mathematical Society*, 22:211–17. - Kircher, A. (1650).
*Musurgia Universalis*, Corbelletti, Rome. - Knuth, Donald E. (1998).
*The Art of Computer Programming*, Vol. 2: Seminumerical Algorithms, Addison Wesley. p. 694. ISBN 0-201-89684-2. - Knuth, D. (1998).
*The Art of Computer Programming*, Vol. 3: Sorting and Searching, Addison-Wesley, Reading, Mass. - Libkin, L. and Wong, L. (1994). Some properties of query languages for bags, in
*Proceedings of the Workshop on Database Programming Languages*, Springer Verlag, pp. 97–114. - Libkin, L. and Wong, L. (1995). On representation and querying incomplete information in databases with bags,
*Information Processing Letters*, 56(4):209–214. - Loeb, D. (1992). Sets with a negative numbers of elements,
*Advances in Mathematics*, 91:64–74. - Miyamoto S. (2001). Fuzzy Multisets and their Generalizations, in ‘'Multiset Processing’', LNCS 2235:225–235.
- Prestet, J. (1675).
*Elemens des Mathematiques*, André Pralard, Paris. - Singh D. (1994) A Note on the Development of Multiset Theory,
*Modern Logic*, 4:405–406. - Singh D, Ibrahim AM, Yohanna T, and Singh JN. (2007) An overview of the applications of multisets,
*Novi Sad Journ. Math.*, 37(2):73–92. - 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. - Yager, R. R. (1986). On the Theory of Bags,
*International Journal of General Systems*, 13:23–37. - Wallis (1685).
*A treatise of algebra*, John Playford, London.