Editing Multiset (section)

{{Short description|Mathematical set with repetitions allowed}}
{{About|the mathematical concept|the computer science data structure|Multiset (abstract data type)}}

In [[mathematics]], a '''multiset''' (or '''bag''', or '''mset''') is a modification of the concept of a [[set (mathematics)|set]] that, unlike a set,<ref name="Cantor">{{cite journal |quote=By a set (Menge) we are to understand any collection into a whole (Zusammenfassung zu einem Gansen) M of definite and '''separate''' objects m  (p.85)|last1=Cantor |first1=Georg |author1link = Georg Cantor|last2=Jourdain |first2=((Philip E.B. (Translator))) |title=beiträge zur begründung der transfiniten Mengenlehre |journal=[[Mathematische Annalen]] |date=1895 |volume=xlvi;xlix |pages=481–512;207–246 |trans-title=contributions to the founding of the theory of transfinite numbers |publisher=New York Dover Publications (1954 English translation) |language=German |url=http://brinkmann-du.de/mathe/fos/fos01_03.htm |archive-url=https://web.archive.org/web/20110610133240/http://brinkmann-du.de/mathe/fos/fos01_03.htm |archive-date=2011-06-10 }}</ref> allows for multiple instances for each of its [[element (mathematics)|element]]s. The number of instances given for each element is called the [[Multiplicity (mathematics)|''multiplicity'']] of that element in the multiset. As a consequence, an infinite number of multisets exist that contain only elements {{mvar|a}} and {{mvar|b}}, but vary in the multiplicities of their elements:
* The set {{math|{{mset|''a'', ''b''}}}} contains only elements {{mvar|a}} and {{mvar|b}}, each having multiplicity 1 when {{math|{{mset|''a'', ''b''}}}} is seen as a multiset.
* In the multiset {{math|{{mset|''a'', ''a'', ''b''}}}}, the element {{mvar|a}} has multiplicity 2, and {{mvar|b}} has multiplicity 1.
* In the multiset {{math|{{mset|''a'', ''a'', ''a'', ''b'', ''b'', ''b''}}}}, {{mvar|a}} and {{mvar|b}} both have multiplicity 3.

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 ''[[tuple]]s'', the order in which elements are listed does not matter in discriminating multisets, so {{math|{{mset|''a'', ''a'', ''b''}}}} and {{math|{{mset|''a'', ''b'', ''a''}}}} denote the same multiset.  To distinguish between sets and multisets, a notation that incorporates square brackets is sometimes used: the multiset {{math|{{mset|''a'', ''a'', ''b''}}}} can be denoted by {{math|[''a'', ''a'', ''b'']}}.<ref>{{cite book|title=Discrete mathematics|url=https://archive.org/details/discretemathemat00hein_966|url-access=limited|first=James L.|last=Hein|publisher=Jones & Bartlett Publishers|year=2003|isbn=0-7637-2210-3|pages=[https://archive.org/details/discretemathemat00hein_966/page/n43 29]–30}}</ref>

The [[cardinality]] or "size" of a multiset is the sum of the multiplicities of all its elements. For example, in the multiset {{math|{{mset|''a'', ''a'', ''b'', ''b'', ''b'', ''c''}}}} the multiplicities of the members {{mvar|a}}, {{mvar|b}}, and {{mvar|c}} are respectively 2, 3, and 1, and therefore the cardinality of this multiset is 6.

[[Nicolaas Govert de Bruijn]] coined the word ''multiset'' in the 1970s, according to [[Donald Knuth]].<ref name="Knuth1998">{{cite book
  | last = Knuth
  | first = Donald E.
  | author-link =Donald Knuth
  | series= [[The Art of Computer Programming]]
  | volume= 2 | title = Seminumerical Algorithms
  | publisher = [[Addison Wesley]]
  | date=1998 | edition = 3rd
  | isbn =0-201-89684-2 }}</ref>{{rp|p=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 [[Bhāskara II|Bhāskarāchārya]], who described [[Permutation#Permutations of multisets|permutations of multisets]] around 1150. Other names have been proposed or used for this concept, including ''list'', ''bunch'', ''bag'', ''heap'', ''sample'', ''weighted set'', ''collection'', and ''suite''.<ref name="Knuth1998"/>{{rp|p=694}}