Multimängd

Från Wikipedia
Hoppa till: navigering, sök

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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[redigera | redigera wikitext]

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 233151, 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[redigera | redigera wikitext]

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)

Referenser[redigera | redigera wikitext]