Multimenge

Multimenge ist ein Begriff aus der Mengenlehre. Die Besonderheit von Multimengen gegenüber dem gewöhnlichen Mengenbegriff besteht darin, dass die Elemente einer Multimenge mehrfach vorkommen können. Dementsprechend haben auch die für Multimengen verwendeten Mengenoperationen eine modifizierte Bedeutung.

In der Informatik stellen Multimengen (dort auch engl. Bag genannt) eine nützliche Datenstruktur dar. Beispielsweise behandelt die Datenbanksprache SQL Tabellen üblicherweise als Multimengen.

Definition

Als Multimenge über einer Menge M bezeichnet man eine Abbildung V von M in die Menge der natürlichen Zahlen. V(x) bezeichnet dann die Vielfachheit des Elementes x aus M.

Anschauung

Anschaulich ist eine Multimenge eine Menge, in der jedes Element beliebig oft vorkommen kann. Man notiert Multimengen dann auch wie Mengen explizit mit geschweiften Klammern und schreibt ein Element so oft hinein, wie es in der Multimenge vorkommt. Mengen sind in diesem Sinne ein Spezialfall von Multimengen, bei denen nur die Werte 0 (nicht enthalten) und 1 (enthalten) zugeordnet werden können.

Halb-abstraktes Beispiel

Sei V die Multimenge über {a,b,c}, mit V(a)=1, V(b)=3 und V(c)=0. Dann schreibt man auch V={a,b,b,b}

Anschauliches Beispiel

Man nehme einen Würfel und würfle 20 mal hintereinander. Dann kann es sein, dass man

3 mal eine 1
2 mal eine 2
4 mal eine 3
5 mal eine 4
3 mal eine 5 und
3 mal eine 6

geworfen hat. Die Grundmenge ist dann {1,2,3,4,5,6}; die Vielfachheit der 3 ist 4; also V(3)=4. Die Multimenge listet jeden Wurf auf, wobei die Reihenfolge außer Acht gelassen wird:

V={1,1,1,2,2,3,3,3,3,4,4,4,4,4,5,5,5,6,6,6}.

Anzahl der möglichen Multimengen

Gegeben sei eine Menge M mit n Elementen. Wie viele Multimengen über M gibt es dann, die k Elemente enthalten? Die Antwort lautet ${n+k-1 \choose k}$

Zur Unterscheidung von normalen Mengen

Um Multimengen von normalen Mengen zu unterscheiden, wird gewöhnlich bei der Aufzählung der Mengen ein kleines b als Index angegeben.

Beispiel $bg=\lbrace x,y,z\rbrace _{b}$

Literatur

• Apostolos Syropoulos: Mathematics of Multisets. In: Multiset Processing. Lecture Notes in Computer Science. Band 2235/2001. Springer, 2001, ISBN 978-3-540-43063-6, S. 347–358, doi:10.1007/3-540-45523-X_17 (duth.gr [PDF]).