Multiset

Nicolaas Govert de Bruijn coined the word multiset in the 1970s, according to Donald Knuth.

Other names have been proposed or used for this concept, including list, bunch, bag, heap, sample, weighted set, collection, and suite.

"[4] These and similar collections of objects can be regarded as multisets, because strokes, tally marks, or units are considered indistinguishable.

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 early AI languages, such as QA4, where they were referred to as bags, a term attributed to Peter Deutsch.

[5]: 320 [7] Although multisets were used implicitly from ancient times, their explicit exploration happened much later.

[3]: 694  The work of Marius 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.

[12][13] Other mathematicians formalized multisets and began to study them as precise mathematical structures in the 20th century.

Monro argued that the concepts of multiset and multinumber are often mixed indiscriminately, though both are useful.

More generally, the fundamental theorem of algebra asserts that the complex solutions of a polynomial equation of degree d always form a multiset of cardinality d. 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.

is a finite set, the multiset (A, m) is often represented as where upper indices equal to 1 are omitted.

If the elements of the multiset are numbers, a confusion is possible with ordinary arithmetic operations; those normally can be excluded from the context.

On the other hand, the latter notation is coherent with the fact that the prime factorization of a positive integer is a uniquely defined multiset, as asserted by the fundamental theorem of arithmetic.

In this view the underlying set of the multiset is given by the image of the family, and the multiplicity of any element x is the number of index values i such that

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.

The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a rising factorial power

is a polynomial in n, it and the generating function are well defined for any complex value of n. The multiplicative formula allows the definition of multiset coefficients to be extended by replacing n 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

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

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.

[17][18][19][20] Multisets have become an important tool in the theory of relational databases, which often uses the synonym bag.

In particular, a table (without a primary key) works as a multiset, because it can have multiple identical records.

In the case that there are multiple records with name "Sara" in the student table, all of them are shown.

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 polynomial f (x) or the spectrum of a linear operator.

"[5]: 328–329 Different generalizations of multisets have been introduced, studied and applied to solving problems.