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 $A\uplus B$, multimängdunion $A\cup B$ och multimängdsnitt $A\cap B$ genom att ett element som har multiplicitet a i A och multiplicitet b i B har multiplicitet

a + b i $A\uplus B$.

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

min(a, b) i $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³3¹5¹, 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 $A\uplus B$, deras största gemensamma delare har primtalsfaktorisering $A\cap B$ och deras minsta gemensamma multipel har primtalsfaktorisering $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 $\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:

$\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:

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

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

Antalet multimängder uppfyller:

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