Multiset

In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist which contain only elements a and b, but vary in the multiplicities of their elements:

Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth.[2]: 694  However, the use of the concept of multisets predates the coinage of the word multiset by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematician Bhāskarāchārya, who described permutations of multisets around 1150. Other names have been proposed or used for this concept, including list, bunch, bag, heap, sample, weighted set, collection, and suite.[2]: 694 

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."[3] These and similar collections of objects are multisets, because strokes, tally marks, or units are considered indistinguishable. This shows that people implicitly used multisets even before mathematics emerged.

Practical needs for this structure have caused multisets to be rediscovered several times, appearing in literature under different names.[4]: 323  For instance, they were important in early AI languages, such as QA4, where they were referred to as bags, a term attributed to Peter Deutsch.[5] A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set).[4]: 320 [6]

Although multisets were used implicitly 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.[2]: 694  The work of Marius Nizolius (1498–1576) contains another early reference to the concept of multisets.[7] Athanasius Kircher found the number of multiset permutations when one element can be repeated.[8] Jean Prestet published a general rule for multiset permutations in 1675.[9] John Wallis explained this rule in more detail in 1685.[10]

Multisets appeared explicitly in the work of Richard Dedekind.[11]: 114 [12]

Other mathematicians formalized multisets and began to study them as precise mathematical structures in the 20th century. For example, Whitney (1933) described generalized sets ("sets" whose characteristic functions may take any integer value - positive, negative or zero).[4]: 326 [13]: 405  Monro (1987) investigated the category Mul of multisets and their morphisms, defining a multiset as a set with an equivalence relation between elements "of the same sort", and a morphism between multisets as a function which respects sorts. He also introduced a multinumber: a function f(x) from a multiset to the natural numbers, giving the multiplicity of element x in the multiset. Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful.[4]: 327–328 [14]

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

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.

It is possible to extend the definition of a multiset by allowing multiplicities of individual elements to be infinite cardinals instead of positive integers, but not all properties carry over to this generalization.

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.

A multiset is finite if its support is finite, or, equivalently, if its cardinality

is finite. The empty multiset is the unique multiset with an empty support (underlying set), and thus a cardinality 0.

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.[citation needed]

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:

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

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

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

The generating function of the multiset coefficients is very simple, being

The multiplicative formula allows the definition of multiset coefficients to be extended by replacing n by an arbitrary number α (negative, real, complex):

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

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.

Multisets have various applications.[6] They are becoming fundamental in combinatorics.[16][17][18][19] Multisets have become an important tool in the theory of relational databases, which often uses the synonym bag.[20][21][22] 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 return 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 set of SQL is a multiset. If it was a set, the repetitive records in the result set were eliminated. Another application of multiset is in modeling multigraphs. In multigraphs there can be multiple edges between any two given vertices. As such, the entity that shows 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 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."[4]: 328–329 

Different generalizations of multisets have been introduced, studied and applied to solving problems.