Multimenge

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

Multimenge ist ein Begriff aus der Informatik. 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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] 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}

[Bearbeiten] 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}.

[Bearbeiten] 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}$