Multi-Menge

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}$

Dies gibt die Anzahl der möglichen Ausgänge beim Ziehen von unterscheidbaren Kugeln aus einer Urne an, wenn die Reihenfolge nicht beachtet wird und eine gezogene Kugel wieder in die Urne zurückgelegt wird, nachdem sie gezogen wurde.

Beispiel

Werden aus einer Urne mit 5 Kugeln nacheinander 10 gezogen, wobei eine gezogene Kugel wieder zurückgelegt wird, so gibt es ${5 + 10 - 1 \choose 10} = 1001$ mögliche Kombination, wenn die Reihenfolge der gezogenen Kugeln nicht beachtet wird.

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 = {x,y,z}_b

Literatur

• Apostolos Syropoulos: Mathematics of Multisets. In: Multiset Processing. Lecture Notes in Computer Science. 2235/2001, Springer, 2001, ISBN 978-3-540-43063-6, S. 347-358 (doi:10.1007/3-540-45523-X_17) (http://obelix.ee.duth.gr/gmcg/Papers/multmath.pdf).