Multimenge

Multimenge i​st ein Begriff, d​er den Mengenbegriff a​us der Mengenlehre variiert. Die Besonderheit v​on Multimengen gegenüber d​em gewöhnlichen Mengenbegriff besteht darin, d​ass die Elemente e​iner Multimenge mehrfach vorkommen können. Dementsprechend h​aben auch d​ie für Multimengen verwendeten Mengenoperationen e​ine modifizierte Bedeutung.

In d​er Informatik stellen Multimengen (dort a​uch engl. Multiset o​der Bag genannt) e​ine nützliche Datenstruktur dar. Beispielsweise behandelt d​ie Datenbanksprache SQL Tabellen standardmäßig a​ls Multimengen.

Definition

Eine Multimenge ${\displaystyle M}$ über einer Menge ${\displaystyle A}$ ist eine Abbildung von ${\displaystyle A}$ in die Menge der natürlichen Zahlen ${\displaystyle \mathbb {N} _{0}}$. Die Zahl ${\displaystyle M(x),x\in A}$ gibt an, wie oft das Element ${\displaystyle x}$ in der Multimenge ${\displaystyle M}$ vorkommt. Die Menge aller Multimengen über ${\displaystyle A}$ kann als ${\displaystyle \mathbb {N} _{0}^{A}}$ geschrieben werden. Im Weiteren wird jedoch, um vertikalen Platz zu sparen, ${\displaystyle \operatorname {MS} (A)}$ verwendet.

Reduzierte Grundmenge

Die reduzierte Grundmenge (engl. „support“) einer Multimenge ${\displaystyle M}$ über ${\displaystyle A}$ ist die Menge ${\displaystyle \operatorname {supp} (M)}$ der relevanten Elemente von ${\displaystyle A}$, in Formeln:

${\displaystyle \operatorname {supp} (M):=\left\{x\in A\mid M(x)>0\right\}}$.

Teilmultimenge

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

${\displaystyle M\subseteq N\quad \Longleftrightarrow \quad \forall x\in \operatorname {supp} (M):M(x)\leq N(x)}$.

Zwei Multimengen ${\displaystyle M}$ und ${\displaystyle N}$ sind gleich, wenn ihre reduzierten Grundmengen gleich sind und die Vielfachheiten übereinstimmen. Sie sind dann auch in beiden Richtungen Teilmultimengen voneinander.

Bemerkung

Obige Definition m​it Zulassung d​es (eigentlich irrelevanten) 0-Wertes i​st eine Verallgemeinerung d​er Indikatorfunktion b​ei den gewöhnlichen Mengen. Sie ermöglicht d​ie Bereitstellung e​ines „Universums“ a​ls Grundmenge, a​uf welches a​lle fraglichen Multimengen bezogen werden, u​nd vereinfacht i​n der Folge Handhabung u​nd Vergleich.

Anschauung

Anschaulich i​st eine Multimenge e​ine Menge, i​n der j​edes Element beliebig o​ft vorkommen kann. Mengen s​ind in diesem Sinne e​in Spezialfall v​on Multimengen, b​ei denen j​eder Wert n​ur genau einmal vorkommt.

Notation

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 ${\displaystyle _{b}}$ (für engl. bag) als Index angefügt. Einige Autoren benutzen stattdessen modifizierte Klammern: ${\displaystyle \{\!\vert \;\;\;\vert \!\}}$.[1]

Halb-abstraktes Beispiel

Es sei ${\displaystyle M}$ die Multimenge über ${\displaystyle \{a,b,c\}}$ mit ${\displaystyle M(a)=1}$, ${\displaystyle M(b)=3}$ und ${\displaystyle M(c)=0}$. Dann schreibt man also ${\displaystyle M=\lbrace a,b,b,b\rbrace }$ oder ${\displaystyle M=\lbrace a,b,b,b\rbrace _{b}}$ oder ${\displaystyle M=\{\!\vert a,b,b,b\vert \!\}}$.

Anschauliche Beispiele

Man n​ehme einen Würfel u​nd würfele 20-mal hintereinander. Dann k​ann es sein, d​ass 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 ${\displaystyle \{1,2,3,4,5,6\}}$; die Vielfachheit der ${\displaystyle 3}$ ist 4; also ${\displaystyle M(3)=4}$. Die Multimenge listet jeden Wurf auf, wobei die Reihenfolge außer Acht gelassen wird:

${\displaystyle M=\{1,1,1,2,2,3,3,3,3,4,4,4,4,4,5,5,5,6,6,6\}.}$

Ein anderes Beispiel i​st etwa d​ie Primfaktorzerlegung v​on 120:

${\displaystyle 120=2^{3}3^{1}5^{1}}$

Sie lässt sich als Multimenge ${\displaystyle \{2,2,2,3,5\}}$ interpretieren.

Anzahl der möglichen Multimengen

Die Anzahl der ${\displaystyle k}$-elementigen Multimengen über einer ${\displaystyle n}$-elementigen Menge ${\displaystyle A}$, wird (analog zu den Binomialkoeffizienten) als ${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)}$ bezeichnet. Dies lässt sich gut als Binomialkoeffizient ausdrücken:

${\displaystyle \left(\!\!{\dbinom {n}{k}}\!\!\right)={\dbinom {k+n-1}{k}}={\dbinom {k+n-1}{n-1}}={\frac {n(n+1)(n+2)\cdots (n+k-1)}{k!}},}$

solange ${\displaystyle k\geq 0}$ und ${\displaystyle n\geq 1}$. Falls ${\displaystyle k=n=0}$, so ist die kombinatorische Größe sinnvoll definiert als ${\displaystyle 1}$. In allen anderen Fällen ist sie gleich ${\displaystyle 0}$.

Dies g​ibt die Anzahl d​er möglichen Ausgänge b​eim Ziehen v​on unterscheidbaren Kugeln a​us einer Urne an, w​enn die Reihenfolge n​icht beachtet w​ird und j​ede gezogene Kugel wieder i​n die Urne zurückgelegt wird, nachdem s​ie gezogen w​urde (siehe Kombination m​it Wiederholung).

Beispiel

Werden a​us einer Urne m​it 5 Kugeln nacheinander 10 gezogen, w​obei jede gezogene Kugel wieder zurückgelegt wird, s​o gibt es

${\displaystyle \left(\!\!{\dbinom {5}{10}}\!\!\right)={\dbinom {10+5-1}{10}}=1001}$

mögliche Kombinationen, w​enn die Reihenfolge d​er gezogenen Kugeln n​icht beachtet wird.

Variante: Multimengen mit mindestens einem Vorkommen von jedem Elementtypen

Bezeichne mit ${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)^{+}}$ die Anzahl der möglichen Multimengen über einer ${\displaystyle n}$-elementigen Menge ${\displaystyle A}$, sodass jeder Elementtyp ${\displaystyle x\in A}$ mindestens ${\displaystyle 1}$-mal vorkommt. Dann ist es leicht zu sehen, dass es sich, sobald die insgesamt ${\displaystyle n}$ obligatorischen Vorkommnisse von den ${\displaystyle k}$ Multimengenobjekten entfernt sind, um eine kombinatorische Aufzählung der ersten Art handelt. Genauer gesagt:

${\displaystyle \left(\!\!{\dbinom {n}{k}}\!\!\right)^{+}=\left(\!\!{\dbinom {n}{k-n}}\!\!\right).}$

Gemäß d​er o. s. Information g​ilt näher

${\displaystyle \left(\!\!{\dbinom {n}{k}}\!\!\right)^{+}={\dbinom {k-1}{n-1}}}$

solange ${\displaystyle k\geq n>0}$. Falls ${\displaystyle k=n=0}$, so ist die kombinatorische Größe sinnvoll definiert als ${\displaystyle 1}$. In allen anderen Fällen ist sie gleich ${\displaystyle 0}$.

Variante: Multimengen mit Kapazitätsbeschränkungen

Bezeichne mit ${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}}$ bzw. ${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)_{\leq c}^{+}}$ die Anzahl der möglichen Multimengen über einer ${\displaystyle n}$-elementigen Menge ${\displaystyle A}$, so dass jeder Elementtyp ${\displaystyle x\in A}$ zwischen ${\displaystyle 0}$ und ${\displaystyle c-1}$ Mal (bzw. zwischen ${\displaystyle 1}$ und ${\displaystyle c}$ Mal) vorkommt. Dies wird regelmäßige Kombination genannt. Mittels kombinatorischer Argumente erhält man die geschlossenen Form:

${\displaystyle \left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}=\sum _{r=0}^{n}(-1)^{r}{\tbinom {n}{r}}\left(\!\!{\tbinom {n}{k-rc}}\!\!\right)}$

und analog für die ${\displaystyle {}^{+}}$-Variante. Zur Herleitung[2] dieser kombinatorischen Größe betrachte man die Mengen

${\displaystyle S=\{M~{\text{Multimenge aus}}~\{0,1,\ldots ,n-1\}\mid \Sigma {}_{x}M(x)=k\};}$

${\displaystyle S_{c}=\{M\in S\mid \forall {x:}\,M(x)<c\};\quad S_{c}(x)=\{M\in S\mid M(x)\geq c\},~x\in \{0,1,\ldots ,n-1\}.}$

und erkennt sofort, dass ${\displaystyle |S_{c}|=\left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}}$ und ${\displaystyle |S|=\left(\!\!{\tbinom {n}{k}}\!\!\right)}$. Man sieht, dass ${\displaystyle S_{c}=\bigcap {}_{x\in \{0,1,\ldots ,n-1\}}S\setminus S_{c}(x)}$, sodass ${\displaystyle |S_{c}|=|S|-|\bigcup {}_{x\in \{1,2,\ldots ,n\}}S_{c}(x)|}$. Mittels einer Bijektionskonstruktion beweist man außerdem, dass ${\displaystyle |\bigcap {}_{x\in I}S_{c}(x)|=\left(\!\!{\tbinom {n}{k-rc}}\!\!\right)}$ für alle ${\displaystyle I\subseteq \{0,1,\ldots ,n-1\}}$ mit ${\displaystyle |I|=r}$. 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 ${\displaystyle {}^{+}}$-Variante herleiten.

Kombinatorische Identitäten: Summen

Um eine ${\displaystyle K}$-elementige Multiset über ${\displaystyle n+1}$ Elementtypen summiert man über die Möglichkeiten für die ${\displaystyle n}$ ersten Elementtypen gegeben die möglichen Werte für die Anzahl des letzten Elemententtyps. Mathematisch ausgedrückt bedeutet dies ${\displaystyle \sum _{k=0}^{K}\left(\!\!{\tbinom {n}{k}}\!\!\right)=\left(\!\!{\tbinom {n+1}{K}}\!\!\right)}$. Die Summendarstellung der beschränkten kombinatorischen Größe ermöglicht nun die Berechnung ihrer kumulativen Summe:

${\displaystyle \sum _{k=0}^{K}\left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}=\sum _{r=0}^{n}(-1)^{r}{\tbinom {n}{r}}\left(\!\!{\tbinom {n+1}{K-rc}}\!\!\right).}$

Anhand der Mengen von Multimengen im o. s. Abschnitt, lässt sich ersehen, dass die Gesamtzahl der Multimengen über ${\displaystyle n}$ Elementen sowie Kapazitätsbeschränkungen gegeben ist durch ${\displaystyle \sum _{k=0}^{\infty }\left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}=c^{n}}$. Dementsprechend kann man die komplementären Summen wie folgt bilden

${\displaystyle \sum _{k>K}\left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}=c^{n}-\sum _{r=0}^{n}(-1)^{r}{\tbinom {n}{r}}\left(\!\!{\tbinom {n+1}{K-rc}}\!\!\right)}$

Die o. s. Ergebnisse gelten analog für die ${\displaystyle {}^{+}}$-Variante. Diese Summen sind u. a. bei der Berechnung von Wahrscheinlichkeiten wichtig.

Beispiel

Die beschränkte kombinatorische Größe kommt vor, wenn ${\textstyle n}$ Typen von Objekten vorhanden sind, davon ${\textstyle 0}$ bis ${\textstyle c-1}$ (bzw. ${\textstyle 1}$–${\textstyle c}$) Kopien pro Typ, und man berechnen will, wie viele ${\textstyle k}$-Kombinationen man daraus selektieren kann (ohne Rücksicht auf die Reihenfolge). Beispielsituationen: (1.) ${\textstyle n=4}$ Kartenfarben, davon ${\textstyle c-1=13}$ Karten und ${\textstyle k=}$Anzahl der Karten. Dann ist ${\textstyle \left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}}$ die Anzahl der möglichen Hände. (2.) ${\textstyle n=}$ Anzahl der Molekülarten mit jeweils ${\textstyle c-1}$ Teilchen und ${\textstyle k=}$Anzahl der Teilchen, die in ein Gefäß fließen. Dann ist ${\textstyle \left(\!\!{\tbinom {n}{k}}\!\!\right)_{<c}}$ die Anzahl der möglichen Mischungen.

Operationen auf Multimengen

Eine Multimenge über Multimengen über ${\displaystyle A}$ kann unter Beachtung der Vielfachheiten vereinigt werden. Dies leistet ${\displaystyle \mu \colon \operatorname {MS} (\operatorname {MS} (A))\to \operatorname {MS} (A)}$, mit

${\displaystyle \mu (M)(a)=\sum _{N\in supp(M)}M(N)\cdot N(a).}$

Eine Funktion ${\displaystyle f\colon A\to B}$ kann erweitert werden zu einer Funktion ${\displaystyle \operatorname {MS} (f)\colon \operatorname {MS} (A)\to \operatorname {MS} (B)}$, wobei

${\displaystyle \operatorname {MS} (f)(M)(b)=\sum _{a\in f^{-1}(b)}M(a).}$

Zusammen mit ${\displaystyle \eta \colon A\to \operatorname {MS} (A)}$ mit

${\displaystyle \eta (a)(a')={\begin{cases}1&a=a'\\0&{\text{sonst}}\end{cases}}}$

haben w​ir es m​it einer Monadenstruktur z​u tun.

Der Funktor ${\displaystyle \operatorname {MS} }$ sowie ${\displaystyle \mu }$ lassen sich auch auf eine andere nützliche Operation zurückführen. ${\displaystyle \operatorname {lift} }$ erweitert eine Funktion ${\displaystyle f\colon A\to \operatorname {MS} (B)}$ zu einer Funktion ${\displaystyle \operatorname {lift} (f)\colon \operatorname {MS} (A)\to \operatorname {MS} (B)}$, und zwar durch

${\displaystyle \operatorname {lift} (f)(M)(b)=\sum _{a\in supp(M)}M(a)\cdot f(a)(b).}$

Mit Hilfe dieser Operation kann ${\displaystyle \mu =\operatorname {lift} (\operatorname {id} )}$ und ${\displaystyle \operatorname {MS} (f)=\operatorname {lift} (\eta \circ f)}$ gesetzt werden.

Vereinigung, Durchschnitt und Differenz

Die (große) Vereinigung zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ kann entweder direkt als

${\displaystyle (M\uplus N)(a)=M(a)+N(a),}$

oder mittels ${\displaystyle \mu }$

${\displaystyle M\uplus N=\mu (\{M,N\}_{b})}$

angegeben werden.

Als kleine Vereinigung zweier Multimengen w​ird die kleinste Multimenge

${\displaystyle (M\cup N)(a)=\operatorname {max} (M(a),N(a))}$,

die b​eide umfasst, angesehen.

Der Durchschnitt zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ ist anwendungsspezifisch. Es gibt

1. ${\displaystyle (M\cap N)(a)=\operatorname {min} (M(a),N(a))}$, sowie
2. ${\displaystyle (M\cap N)(a)=M(a)\cdot N(a).}$

Die zweite Definition lässt sich auf obiges ${\displaystyle \operatorname {lift} }$ zurückführen, wenn zusätzlich eine weitere Operation eingeführt wird. Sei ${\displaystyle f\colon A\times B\to \operatorname {MS} (C)}$, dann ist ${\displaystyle \operatorname {lift} _{2}(f)\colon \operatorname {MS} (A)\times \operatorname {MS} (B)\to \operatorname {MS} (C)}$ definiert durch

${\displaystyle \operatorname {lift} _{2}(f)(M,N)=\operatorname {lift} (a\mapsto \operatorname {lift} (b\mapsto f(a,b))(N))(M)}$.

Der Durchschnitt im zweiten Sinne ergibt sich dann als ${\displaystyle M\cap N=\operatorname {lift} _{2}(h)(M,N)}$ mit

${\displaystyle h(a,a')={\begin{cases}\{a\}_{b}&a=a'\\\emptyset &{\text{sonst}}.\end{cases}}}$

Für die Differenz zweier Multimengen über derselben Grundmenge ${\displaystyle A}$ gibt es ebenfalls mindestens zwei sinnvolle Definitionen.

1. ${\displaystyle (M\setminus N)(a)={\begin{cases}0&M(a)<N(a)\\M(a)-N(a)&{\text{sonst}}\end{cases}}}$
2. ${\displaystyle (M\setminus N)(a)={\begin{cases}0&N(a)\neq 0\\M(a)&{\text{sonst}}.\end{cases}}}$

Für beide gilt ${\displaystyle X\setminus \emptyset =X}$ und ${\displaystyle X\setminus X=\emptyset }$. Welche die "richtige" ist, hängt vom Anwendungsfall ab.

Bemerkung:
Seien ${\displaystyle M,N}$ Multimengen über den Primzahlen. Mit ${\displaystyle m:=\Pi M}$ und ${\displaystyle n:=\Pi N}$ als ausmultiplizierten Multimengen haben wir:

• Die große Vereinigung entspricht dem Produkt ${\displaystyle m\cdot n}$.
• Die kleine Vereinigung entspricht dem kgV, d. h. ${\displaystyle \operatorname {kgV} (m,n)=\Pi {M\cup N}}$.
• Die erste Version des Durchschnitts entspricht dem ggT, d. h. ${\displaystyle \operatorname {ggT} (m,n)=\Pi {M\cap N}}$.
• Die erste Version der Differenz entspricht ${\displaystyle m/\operatorname {ggT} (m,n)}$.

Verallgemeinerungen

Behält m​an die i​m vorangegangenen Abschnitt definierten Operationen bei, erhält m​an durch Variation d​er Vielfachheitenmenge verwandte Strukturen.

• Reelle Vielfachheiten im Intervall ${\displaystyle [0,1]}$ ergeben Wahrscheinlichkeitsverteilungen. Die Multimengen-Grundmenge wird zur Menge möglicher Ereignisse. Die ${\displaystyle \operatorname {lift} }$-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. ${\displaystyle \operatorname {lift} }$ verkörpert dabei die Tatsache, dass es für die Festlegung einer linearen Abbildung ausreicht, die Bilder der Basisvektoren festzulegen. Auf ähnliche Weise rechnet ${\displaystyle \operatorname {lift} _{2}}$ Funktionen auf Basisindexpaaren in bilineare Abbildungen um.

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 (PDF).

Einzelnachweise

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: Permutation and combinations. In: An Introduction to Combinatorial Analysis (en). John Wiley & Sons Inc., 1958, S. 16.