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.

[9] Jean Prestet published a general rule for multiset permutations in 1675.

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

This is equivalent to saying that their intersection is the empty multiset or that their sum equals their union.

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:

The number of characters including both dots and vertical lines used in this notation is 18 + 4 − 1.

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.

Similarly, SQL operates on multisets and returns 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.