Multiset

In de wiskunde is een multiset (uit het Engels: multiset of bag (zak)) een generalisatie van het concept verzameling. Een element van een multiset kan meer dan één keer in de multiset voorkomen, dit in tegenstelling tot een verzameling, waarin elk element precies één keer voorkomt. De term "multiset" werd in de jaren zeventig van de twintigste eeuw geïntroduceerd door Nicolaas Govert de Bruijn.^[1] Het gebruik van multisets in wiskunde gaat echter vooraf aan de introductie van de term 'multiset'. In 1888 gebruikte Richard Dedekind het concept al in een van zijn artikelen.^[2]

Het aantal keren dat eenzelfde element voorkomt in een multiset, wordt de multipliciteit van dat element genoemd. In de multiset {a, a, b, b, c, b} bijvoorbeeld is de multipliciteit van de elementen a, b en c respectievelijk 2, 3 en 1.

Het totale aantal elementen in een multiset is de som van de multipliciteiten van de elementen en wordt de kardinaliteit van de multiset genoemd. De kardinaliteit van de multiset {a, a, b, b, c, b} is 6.

Net als in verzamelingen, maar in tegenstelling tot tupels, is de volgorde van elementen in multisets niet van belang. De onderstaande drie voorbeelden illustreren de verschillen tussen de concepten:

• De tupels (a, b) en (b, a), met a ≠ b, zijn niet aan elkaar gelijk, aangezien in tupels de volgorde van belang is; ook de tupels (a, a) en (a) zijn niet aan elkaar gelijk, omdat in tupels en multisets de multipliciteit van belang is, waardoor de kardinaliteit verschilt.
• De multisets {a, b} en {b, a} zijn aan elkaar gelijk, omdat in multisets de volgorde niet van belang is, maar de multisets {a, a} en {a} zijn niet dezelfde, aangezien zij verschillende kardinaliteiten hebben. Wel zijn de verzamelingen {a, a} en {a} aan elkaar gelijk.
• De verzamelingen {a, b} en {b, a} zijn aan elkaar gelijk, net als de multisets {a, b} en {b, a}.

Er is geen eenduidige notatie voor een multiset. Het is gebruikelijk een multiset als zodanig te benoemen en te noteren als een verzameling en de gelijke elementen te herhalen. Een eenvoudig voorbeeld van een multiset is: {1,2,2,2,3,3}, met de elementen 1 met multipliciteit 1, 2 met multipliciteit 3 en 3 met multipliciteit 2. Men dient te weten dat het hier om een multiset gaat, want als verzameling opgevat geldt: {1,2,2,2,3,3} = {1,2,3}.

1. ↑ Knuth, Donald E. (1998). The Art of Computer Programming - Vol. 2: Seminumerical Algorithms, 3e editie. Addison Wesley, pp. 694. ISBN 0201896842. Knuth geeft in zijn boek ook andere namen voor multisets, zoals list (lijst), bunch (bundel), bag (tas), heap (stapel), sample (staal), weighted set (gewogen verzameling), collection (collectie), suite (stel).
2. ↑ Syropoulos, Apostolos (2001), p. 347.