Multiset

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, a multiset (or bag, or mset) is a modification of the concept of a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> that, unlike a set, allows for multiple instances for each of its <a href="/facts/Element_(mathematics)/Q2mx1vHL">elements</a>. The number of instances given for each element is called the <a href="/facts/Multiplicity_(mathematics)/dndUyetA">multiplicity</a> of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements a and b, but vary in the multiplicities of their elements:

<ul><li>The set {a, b} contains only elements a and b, each having multiplicity 1 when {a, b} is seen as a multiset.</li>
<li>In the multiset {a, a, b}, the element a has multiplicity 2, and b has multiplicity 1.</li>
<li>In the multiset {a, a, a, b, b, b}, a and b both have multiplicity 3.</li></ul>
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 to <a href="/facts/Tuple/BI1HIxL8">tuples</a>, 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].
The <a href="/facts/Cardinality/m6VPojwT">cardinality</a> 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 members a, b, and c are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.
<a href="/facts/Nicolaas_Govert_de_Bruijn/pr2Hbxfm">Nicolaas Govert de Bruijn</a> coined the word multiset in the 1970s, according to <a href="/facts/Donald_Knuth/GozNzDM6">Donald Knuth</a>.: 694  However, 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 <a href="/facts/Bh%25C4%2581skara_II/BQlUY9gA">Bhāskarāchārya</a>, who described <a href="/facts/Permutation/JSw9ukmv">permutations of multisets</a> around 1150. Other names have been proposed or used for this concept, including list, bunch, bag, heap, sample, weighted set, collection, and suite.: 694

Multiset open-in-new

Multiset