Multimängd

En multimängd är inom matematik en generalisering av begreppet mängd. En multimängd kan till skillnad från en mängd innehålla ett element flera gånger. I likhet med en mängd spelar dock inte ordningen av elementen någon roll i en multimängd. Det antal gånger ett element förekommer i en multimängd kallas för elementets multiplicitet. Antalet element i en multimängd, medräknat element som förekommer flera gånger, kallas för multimängdens kardinalitet.

Formell definition

En multimängd definieras formellt som ett par (S, m) av en mängd S och en funktion m från S till de positiva heltalen. Funktionen m är multipliciteten för ett elementen i S, dvs, hur många gånger varje element förekommer i multimängden.

Om S är en mängd i ett universum U kan definitionen av en multimängd förenklas till att vara endast en funktion m från U till de naturliga talen, då m antar värdet 0 för de element som inte är i mängden.

Operationer på multimängder

Om A och B är multimängder kan man definiera operationerna multimängdsumma ${\displaystyle A\uplus B}$, multimängdunion ${\displaystyle A\cup B}$ och multimängdsnitt ${\displaystyle A\cap B}$ genom att ett element som har multiplicitet a i A och multiplicitet b i B har multiplicitet

a + b i ${\displaystyle A\uplus B}$.

max(a, b) i ${\displaystyle A\cup B}$.

min(a, b) i ${\displaystyle A\cap B}$.

Exempel

Ett heltal n kan faktoriseras unikt i primtal (upp till ordningen på faktorerna) och denna faktorisering kan uttryckas som en multimängd. Exempelvis kan 120 faktoriseras som 2^33^15^1, vilket vi kan uttrycka som multimängden {2, 2, 2, 3, 5}. Den underliggande mängden är i detta fallet alla primtalsfaktorer i n.

Om två tal a och b har primtalsfaktoriseringar A och B, uttryckta som multimängder så får man att deras produkt ab har primtalsfaktorisering ${\displaystyle A\uplus B}$, deras största gemensamma delare har primtalsfaktorisering ${\displaystyle A\cap B}$ och deras minsta gemensamma multipel har primtalsfaktorisering ${\displaystyle A\cup B}$.

Antal multimängder

Antalet multimängder med kardinalitet k där elementen tas från en mängd med ändlig kardinalitet n brukar betecknas ${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)}$. Notationen är vald för att likna den för binomialkoefficienter, som även kan användas för att räkna ut talet:

${\displaystyle \left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)(n+k-2)\cdots (n+1)n}{k!}}={\frac {n^{\overline {k}}}{k!}}}$

där täljaren i sista bråket är en ökande potens. Detta kan jämföras med att binomialkoefficient kan skrivas som:

${\displaystyle {n \choose k}={\frac {n^{\underline {k}}}{k!}}}$

där täljaren i bråket är en fallande potens.

Antalet multimängder uppfyller:

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

Se även

• Mängdlära

Referenser

• Stanley, Richard P. (1986). Enumerative Combinatorics. ISBN 0-534-06546-5 
• Knuth, Donald (1998). The Art of Computer Programming, Volume 2, Seminumerical Algorithms. Addison-Wesley. ISBN 978-0-201-89684-8