Inmathematics, amultiset (orbag, ormset) is a modification of the concept of aset that, unlike a set,[1] allows for multiple instances for each of itselements. The number of instances given for each element is called themultiplicity of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elementsa andb, but vary in the multiplicities of their elements:
These objects are all different when viewed as multisets, although they are the same set, since they all consist of the same elements. As with sets, and in contrast totuples, the order in which elements are listed does not matter in discriminating multisets, so{a,a,b} and{a,b,a} denote the same multiset. To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset{a,a,b} can be denoted by[a,a,b].[2]
Thecardinality or "size" of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset{a,a,b,b,b,c} the multiplicities of the membersa,b, andc are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.
Nicolaas Govert de Bruijn coined the wordmultiset in the 1970s, according toDonald Knuth.[3]: 694 However, the concept of multisets predates the coinage of the wordmultiset by many centuries. Knuth himself attributes the first study of multisets to the Indian mathematicianBhāskarāchārya, who describedpermutations of multisets around 1150. Other names have been proposed or used for this concept, includinglist,bunch,bag,heap,sample,weighted set,collection, andsuite.[3]: 694
Wayne Blizard traced multisets back to the very origin of numbers, arguing that "in ancient times, the numbern was often represented by a collection ofn strokes,tally marks, or units."[4] These and similar collections of objects can be regarded as 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.[5]: 323 For instance, they were important in earlyAI languages, such as QA4, where they were referred to asbags, a term attributed toPeter Deutsch.[6] A multiset has been also called an aggregate, heap, bunch, sample, weighted set, occurrence set, and fireset (finitely repeated element set).[5]: 320 [7]
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 mathematicianBhāskarāchārya circa 1150, who described permutations of multisets.[3]: 694 The work ofMarius Nizolius (1498–1576) contains another early reference to the concept of multisets.[8]Athanasius Kircher found the number of multiset permutations when one element can be repeated.[9]Jean Prestet published a general rule for multiset permutations in 1675.[10]John Wallis explained this rule in more detail in 1685.[11]
Multisets appeared explicitly in the work ofRichard Dedekind.[12][13]
Other mathematicians formalized multisets and began to study them as precise mathematical structures in the 20th century. For example,Hassler Whitney (1933) describedgeneralized sets ("sets" whosecharacteristic functions may take anyinteger value: positive, negative or zero).[5]: 326 [14]: 405 Monro (1987) investigated thecategoryMul of multisets and theirmorphisms, defining amultiset as a set with anequivalence relation between elements "of the samesort", and amorphism between multisets as afunction that respectssorts. He also introduced amultinumber: a functionf (x) from a multiset to thenatural numbers, giving themultiplicity of elementx in the multiset. Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful.[5]: 327–328 [15]
One of the simplest and most natural examples is the multiset ofprime factors of a natural numbern. Here the underlying set of elements is the set of prime factors ofn. For example, the number120 has theprime factorizationwhich gives the multiset{2, 2, 2, 3, 5}.
A related example is the multiset of solutions of analgebraic equation. Aquadratic 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, thefundamental theorem of algebra asserts that thecomplex solutions of apolynomial equation ofdegreed always form a multiset of cardinalityd.
A special case of the above are theeigenvalues of amatrix, whose multiplicity is usually defined as their multiplicity asroots of thecharacteristic polynomial. However two other multiplicities are naturally defined for eigenvalues, their multiplicities as roots of theminimal polynomial, and thegeometric multiplicity, which is defined as thedimension of thekernel ofA −λI (whereλ is an eigenvalue of the matrixA). These three multiplicities define three multisets of eigenvalues, which may be all different: LetA be an × n matrix inJordan normal form that has a single eigenvalue. Its multiplicity isn, 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.
Amultiset may be formally defined as anordered pair(U,m) whereU is aset called auniverse or theunderlying set, and is a function fromU to thenonnegative integers. The value for an element is called themultiplicity of in the multiset and intepreted as the number of occurrences of in the multiset.
Thesupport of a multiset is the subset of formed by the elements such that. Afinite multiset is a multiset with afinite support. Most authors definemultisets as finite multisets. This is the case in this article, where, unless otherwise stated, all multisets are finite multisets.
Some authors[16] define multisets with the additional constraint that for every, or, equivalently, the support equals the underlying set.Multisets with infinite multiplicities have also been studied;[17] they are not considered in this article.Some authors[who?] define a multiset in terms of a finite index set and a function where the multiplicity of an element is, the number of elements of that get mapped to by.
Multisets may be represented as sets, with some elements repeated. For example, the multiset with support and multiplicity function such that can be represented as{a,a,b}. A more compact notation, in case of high multiplicities is for the same multiset.
If a multiset with support included in is often represented asto which the computation rules ofindeterminates 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 An advantage of notation is that it allows using the notation without knowing the exact support. For example, theprime factors of anatural number form a multiset such that
The finite subsets of a set are exactly the multisets with underlying set, such that for every.
Elements of a multiset are generally taken in a fixed setU, sometimes called auniverse, which is often the set ofnatural numbers. An element ofU 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 fromU to the set of non-negative integers. This defines aone-to-one correspondence between these functions and the multisets that have their elements inU.
This extended multiplicity function is commonly called simply themultiplicity function, and suffices for defining multisets when the universe containing the elements has been fixed. This multiplicity function is a generalization of theindicator function of asubset, and shares some properties with it.
Thesupport of a multiset in a universeU is the underlying set of the multiset. Using the multiplicity function, it is characterized as
A multiset isfinite if its support is finite, or, equivalently, if its cardinalityis finite. Theempty multiset is the unique multiset with anempty 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 andB are multisets in a given universeU, with multiplicity functions and
Two multisets aredisjoint if their supports aredisjoint 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 tothe 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 anodd number of the given multisets, while in the second sum we consider all possible intersections of aneven number of the given multisets.[citation needed]
The number of multisets of cardinalityk, with elements taken from a finite set of cardinalityn, is sometimes called themultiset coefficient ormultiset number. This number is written by some authors as, a notation that is meant to resemble that ofbinomial coefficients; it is used for instance in (Stanley, 1997), and could be pronounced "n multichoosek" to resemble "n choosek" for Like thebinomial distribution that involves binomial coefficients, there is anegative binomial distribution in which the multiset coefficients occur. Multiset coefficients should not be confused with themultinomial coefficients that occur in themultinomial theorem.
The value of multiset coefficients can be given explicitly aswhere the second expression is as a binomial coefficient;[a] 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 cardinalityk of a set of cardinalityn +k − 1. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as arising factorial powerto match the expression of binomial coefficients using a falling factorial power:
For example, there are 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 4subsets 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 toprove 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} (6as, 2bs, 3cs, 7ds) in this form:
This is a multiset of cardinalityk = 18 made of elements of a set of cardinalityn = 4. The number of characters including both dots and vertical lines used in this notation is18 + 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 the4 − 1 vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 of a set of cardinality18 + 4 − 1. Equivalently, it is the number of ways to arrange the 18 dots among the18 + 4 − 1 characters, which is the number of subsets of cardinality 18 of a set of cardinality18 + 4 − 1. This isthus is the value of the multiset coefficient and its equivalencies:
From the relation between binomial coefficients and multiset coefficients, it follows that the number of multisets of cardinalityk in a set of cardinalityn can be writtenAdditionally,
Arecurrence relation for multiset coefficients may be given aswith
The above recurrence may be interpreted as follows.Let be the source set. There is always exactly one (empty) multiset of size 0, and ifn = 0 there are no larger multisets, which gives the initial conditions.
Now, consider the case in whichn,k > 0. A multiset of cardinalityk with elements from[n] might or might not contain any instance of the final elementn. If it does appear, then by removingn once, one is left with a multiset of cardinalityk − 1 of elements from[n], and every such multiset can arise, which gives a total of possibilities.
Ifn does not appear, then our original multiset is equal to a multiset of cardinalityk with elements from[n − 1], of which there are
Thus,
Thegenerating function of the multiset coefficients is very simple, beingAs multisets are in one-to-one correspondence withmonomials, is also the number of monomials ofdegreed inn indeterminates. Thus, the above series is also theHilbert series of thepolynomial ring
As is a polynomial inn, it and the generating function are well defined for anycomplex value ofn.
The multiplicative formula allows the definition of multiset coefficients to be extended by replacingn by an arbitrary numberα (negative,real, or complex):
With this definition one has a generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the negative binomial coefficients:
ThisTaylor series formula is valid for all complex numbersα andX with|X| < 1. It can also be interpreted as anidentity offormal power series inX, 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 forexponentiation, notably
and formulas such as these can be used to prove identities for the multiset coefficients.
Ifα is a nonpositive integern, then all terms withk > −n are zero, and the infinite series becomes a finite sum. However, for other values ofα, including positive integers andrational numbers, the series is infinite.
Multisets have various applications.[7] They are becoming fundamental incombinatorics.[18][19][20][21] Multisets have become an important tool in the theory ofrelational databases, which often uses the synonymbag.[22][23][24] 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 modelingmultigraphs. In multigraphs there can be multiple edges between any two givenvertices. 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 polynomialf (x) or thespectrum of alinear operator."[5]: 328–329
Different generalizations of multisets have been introduced, studied and applied to solving problems.
Learning materials related toPartitions of multisets at WikiversityBy a set (Menge) we are to understand any collection into a whole (Zusammenfassung zu einem Gansen) M of definite andseparate objects m (p.85)
{{cite book}}: CS1 maint: location missing publisher (link)