Multiset

A multiset is an 2-tulple (S, f), where [math]\displaystyle{ S }[/math] is a set and [math]\displaystyle{ f }[/math] is a frequency function (that returns the Frequency of a multiset member).

• AKA: Bag, Unordered Sequence.
• Context:
  • It can be represented by a Frequency Table, or a Multiset Data Structure.
  • It can be transformed by a Multiset Operation.
  • It can range from being an Unordered Multiset to being an Ordered Multiset (e.g. a Tuple such as a Vector).
  • It can range from being an Infinite Multiset to being a Finite Multiset (e.g. a Tuple of the marks reported for an course exam.).
• Example(s):
  • M={a}.
  • M={a, a}.
  • M={1.1, 0.9, 1.1, 2.4}, a record of Experimental Measurement.
  • {a, b, a} = {b, a, a}, a Multiset Operation.
  • {a, b, a, a} ≠ {b, a, a}, a Multiset Operation.
  • A Bag of Words.
  • {A/6, B/11, C+/20, ..., F/2}, a set of marks reported for an course exam.
  • {(a,1), (b,2), (a,1)}, a Tuple Multiset.
  • A set of roots of a polynomial.
  • a set of Sensor Values.
  • a set of Random Experiments.
  • …
• Counter-Example(s):
  • (a, b, a) ≠ (b, a, a), a Tuple Operation.
• See: Ordered Set, Set (Mathematics).

---

---

References

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/multiset Retrieved:2014-4-21.
  • In mathematics, the notion of multiset (or bag) is a generalization of the notion of set in which members are allowed to appear more than once. For example, there is a unique set that contains the elements a and b and no others, but there are many multisets with this property, such as the multiset that contains two copies of a and one of b or the multiset that contains three copies of both a and b. The term "multiset" was coined by Nicolaas Govert de Bruijn in the 1970s.

    The use of multisets in mathematics and beyond predates the name "multiset" by many centuries: Knuth (1998) attributes the first study of multisets to the Indian mathematician Bhascara Acharya (circa 1150), who described permutations of multisets.

---