Multimenge ist ein Begriff, der den Mengenbegriff aus der Mengenlehre variiert. 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. Multiset oder Bag genannt) eine nützliche Datenstruktur dar. Beispielsweise behandelt die Datenbanksprache SQL Tabellen standardmäßig als Multimengen.

Definition

Bearbeiten

Eine Multimenge   über einer Menge   ist eine Abbildung von   in die Menge der natürlichen Zahlen  . Die Zahl   gibt an, wie oft das Element   in der Multimenge   vorkommt. Die Menge aller Multimengen über   kann als   geschrieben werden. Im Weiteren wird jedoch, um vertikalen Platz zu sparen,   verwendet.

Reduzierte Grundmenge

Bearbeiten

Die reduzierte Grundmenge (engl. „support“) einer Multimenge   über   ist die Menge   der relevanten Elemente von  , in Formeln:

 .

Teilmultimenge

Bearbeiten

Eine Multimenge   heißt Teil(multi)menge einer Multimenge  , wenn jedes Element der reduzierten Grundmenge von   in   mindestens so häufig vorkommt wie in  . Formal:

 .

Zwei Multimengen   und   sind gleich, wenn ihre reduzierten Grundmengen gleich sind und die Vielfachheiten übereinstimmen. Sie sind dann auch in beiden Richtungen Teilmultimengen voneinander.

Bemerkung

Bearbeiten

Obige Definition mit Zulassung des (eigentlich irrelevanten) 0-Wertes ist eine Verallgemeinerung der Indikatorfunktion bei den gewöhnlichen Mengen. Sie ermöglicht die Bereitstellung eines „Universums“ als Grundmenge, auf welches alle fraglichen Multimengen bezogen werden, und vereinfacht in der Folge Handhabung und Vergleich.

Anschauung

Bearbeiten

Anschaulich ist eine Multimenge eine Menge, in der jedes Element beliebig oft vorkommen kann. Mengen sind in diesem Sinne ein Spezialfall von Multimengen, bei denen jedes Element nur genau einmal vorkommt.

Notation

Bearbeiten

Man notiert Multimengen wie Mengen explizit mit geschweiften Klammern und schreibt ein Element so oft hinein, wie es in der Multimenge vorkommt. Um Multimengen von normalen Mengen zu unterscheiden, wird bei ihrer Aufzählung gelegentlich auch ein kleines   (für engl. bag) als Index angefügt. Einige Autoren benutzen stattdessen modifizierte Klammern:  .[1]

Halb-abstraktes Beispiel

Bearbeiten

Es sei   die Multimenge über   mit  ,   und  . Dann schreibt man also   oder   oder  .

Anschauliche Beispiele

Bearbeiten

Man nehme einen Würfel und würfele 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  ; die Vielfachheit der   ist 4; also  . Die Multimenge listet jeden Wurf auf, wobei die Reihenfolge außer Acht gelassen wird:

 

Ein anderes Beispiel ist etwa die Primfaktorzerlegung von 120:

 

Sie lässt sich als Multimenge   interpretieren.

Anzahl der möglichen Multimengen

Bearbeiten

Die Anzahl der  -elementigen Multimengen über einer  -elementigen Menge   wird (analog zu den Binomialkoeffizienten) als   bezeichnet. Dies lässt sich gut als Binomialkoeffizient ausdrücken:

 

solange   und  . Falls  , so ist die kombinatorische Größe sinnvoll definiert als  . In allen anderen Fällen ist sie gleich  .

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 jede gezogene Kugel wieder in die Urne zurückgelegt wird, nachdem sie gezogen wurde (siehe Kombination mit Wiederholung).

Beispiel

Bearbeiten

Werden aus einer Urne mit 5 Kugeln nacheinander 10 gezogen, wobei jede gezogene Kugel wieder zurückgelegt wird, so gibt es

 

mögliche Kombinationen, wenn die Reihenfolge der gezogenen Kugeln nicht beachtet wird.

Variante: Multimengen mit mindestens einem Vorkommen von jedem Elementtypen

Bearbeiten

Bezeichne mit   die Anzahl der möglichen Multimengen über einer  -elementigen Menge  , sodass jeder Elementtyp   mindestens  -mal vorkommt. Dann ist es leicht zu sehen, dass es sich, sobald die insgesamt   obligatorischen Vorkommnisse von den   Multimengenobjekten entfernt sind, um eine kombinatorische Aufzählung der ersten Art handelt. Genauer gesagt:

 

Gemäß der o. s. Information gilt näher

 

solange  . Falls  , so ist die kombinatorische Größe sinnvoll definiert als  . In allen anderen Fällen ist sie gleich  .

Variante: Multimengen mit Kapazitätsbeschränkungen

Bearbeiten

Bezeichne mit   bzw.   die Anzahl der möglichen Multimengen über einer  -elementigen Menge  , so dass jeder Elementtyp   zwischen   und   Mal (bzw. zwischen   und   Mal) vorkommt. Dies wird regelmäßige Kombination genannt. Mittels kombinatorischer Argumente erhält man die geschlossenen Form:

 

und analog für die  -Variante. Zur Herleitung[2] dieser kombinatorischen Größe betrachte man die Mengen

 
 

und erkennt sofort, dass   und  . Man sieht, dass  , sodass  . Mittels einer Bijektionskonstruktion beweist man außerdem, dass   für alle   mit  . Anhand dieser Erkenntnisse sowie der Inklusion-Exlusion-Formel für die Kardinalität einer endlichen Vereinigung lässt sich die o. s. geschlossene Form berechnen. Analog kann man die  -Variante herleiten.

Kombinatorische Identitäten: Summen

Bearbeiten

Um eine  -elementige Multiset über   Elementtypen summiert man über die Möglichkeiten für die   ersten Elementtypen gegeben die möglichen Werte für die Anzahl des letzten Elemententtyps. Mathematisch ausgedrückt bedeutet dies  . Die Summendarstellung der beschränkten kombinatorischen Größe ermöglicht nun die Berechnung ihrer kumulativen Summe:

 

Anhand der Mengen von Multimengen im o. s. Abschnitt, lässt sich ersehen, dass die Gesamtzahl der Multimengen über   Elementen sowie Kapazitätsbeschränkungen gegeben ist durch  . Dementsprechend kann man die komplementären Summen wie folgt bilden

 

Die o. s. Ergebnisse gelten analog für die  -Variante. Diese Summen sind u. a. bei der Berechnung von Wahrscheinlichkeiten wichtig.

Beispiel

Bearbeiten

Die beschränkte kombinatorische Größe kommt vor, wenn   Typen von Objekten vorhanden sind, davon   bis   (bzw.   ) Kopien pro Typ, und man berechnen will, wie viele  -Kombinationen man daraus selektieren kann (ohne Rücksicht auf die Reihenfolge). Beispielsituationen: (1.)   Kartenfarben, davon   Karten und  Anzahl der Karten. Dann ist   die Anzahl der möglichen Hände. (2.)   Anzahl der Molekülarten mit jeweils   Teilchen und  Anzahl der Teilchen, die in ein Gefäß fließen. Dann ist   die Anzahl der möglichen Mischungen.

Operationen auf Multimengen

Bearbeiten

Eine Multimenge über Multimengen über   kann unter Beachtung der Vielfachheiten vereinigt werden. Dies leistet  , mit

 

Eine Funktion   kann erweitert werden zu einer Funktion  , wobei

 

Zusammen mit   mit

 

haben wir es mit einer Monadenstruktur zu tun.

Der Funktor   sowie   lassen sich auch auf eine andere nützliche Operation zurückführen.   erweitert eine Funktion   zu einer Funktion  , und zwar durch

 

Mit Hilfe dieser Operation kann   und   gesetzt werden.

Vereinigung, Durchschnitt und Differenz

Bearbeiten

Die (große) Vereinigung zweier Multimengen über derselben Grundmenge   kann entweder direkt als

 

oder mittels  

 

angegeben werden.

Als kleine Vereinigung zweier Multimengen wird die kleinste Multimenge

 ,

die beide umfasst, angesehen.

Der Durchschnitt zweier Multimengen über derselben Grundmenge   ist anwendungsspezifisch. Es gibt

  1.  , sowie
  2.  

Die zweite Definition lässt sich auf obiges   zurückführen, wenn zusätzlich eine weitere Operation eingeführt wird. Sei  , dann ist   definiert durch

 .

Der Durchschnitt im zweiten Sinne ergibt sich dann als   mit

 

Für die Differenz zweier Multimengen über derselben Grundmenge   gibt es ebenfalls mindestens zwei sinnvolle Definitionen.

  1.  
  2.  

Für beide gilt   und  . Welche die "richtige" ist, hängt vom Anwendungsfall ab.

Bemerkung:
Seien   Multimengen über den Primzahlen. Mit   und   als ausmultiplizierten Multimengen haben wir:

  • Die große Vereinigung entspricht dem Produkt  .
  • Die kleine Vereinigung entspricht dem kgV, d. h.  .
  • Die erste Version des Durchschnitts entspricht dem ggT, d. h.  .
  • Die erste Version der Differenz entspricht  .

Verallgemeinerungen

Bearbeiten

Behält man die im vorangegangenen Abschnitt definierten Operationen bei, erhält man durch Variation der Vielfachheitenmenge verwandte Strukturen.

  • Reelle Vielfachheiten im Intervall   ergeben Wahrscheinlichkeitsverteilungen. Die Multimengen-Grundmenge wird zur Menge möglicher Ereignisse. Die  -Operation rechnet Funktionen, die auf der Basis von eingetretenen Ereignissen Wahrscheinlichkeitsverteilungen anderer Ereignismengen erzeugen, in solche um, die mit Wahrscheinlichkeitsverteilungen als Eingabe umgehen können. Vergleiche auch Fuzzymengen.
  • Lässt man für die Vielfachheiten Körperelemente zu und definiert zusätzlich eine Skalierung, werden Multimengen über A zu Vektoren eines Vektorraums mit einer Basis, die durch A indiziert wird.   verkörpert dabei die Tatsache, dass es für die Festlegung einer linearen Abbildung ausreicht, die Bilder der Basisvektoren festzulegen. Auf ähnliche Weise rechnet   Funktionen auf Basisindexpaaren in bilineare Abbildungen um.

Literatur

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Cristian S. Calude, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, Multiset Processing: Mathematical, Computer Science, and Molecular Computing Points of View Springer Verlag 2001, ISBN 3-540-43063-6, S. 105
  2. John Riordan: An Introduction to Combinatorial Analysis. John Wiley & Sons Inc., 1958, Permutation and combinations, S. 16 (englisch).