Multiset

Den här artikeln handlar om det matematiska konceptet. För datavetenskapens datastruktur, se Multiset (abstrakt datatyp) .

I matematik är en multiset (eller påse eller mset ) en modifiering av begreppet en uppsättning som, till skillnad från en uppsättning, tillåter flera instanser för vart och ett av dess element . Antalet instanser som ges för varje element kallas multipliciteten av det elementet i multiuppsättningen. Som en konsekvens existerar ett oändligt antal multiset som bara innehåller elementen a och b , men som varierar i mångfalden av deras element:

• Mängden { a , b } innehåller endast element a och b , var och en har multiplicitet 1 när { a , b } ses som en multimängd.
• I multimängden { a , a , b } har elementet a multiplicitet 2 och b har multiplicitet 1.
• I multimängden { a , a , a , b , b , b } , a och b har båda multipliciteten 3.

Dessa objekt är alla olika när de ses som multiset, även om de är samma uppsättning, eftersom de alla består av samma element. Som med mängder, och i motsats till tupler , spelar ordningen i vilka element listas ingen roll vid särskiljande av multimängder, så { a , a , b } och { a , b , a } betecknar samma multiset. För att skilja mellan mängder och multimängder används ibland en notation som innehåller hakparenteser: multimängden { a , a , b } kan betecknas med [ a a , b ] . ,

Kardinaliteten för en multiset är summan av multipliciteten av alla dess element . Till exempel, i multimängden { a , a , b , b , b , c } är multipliciteten av medlemmarna a , b , och c respektive 2, 3 och 1, och därför är kardinaliteten för denna multiset 6.

Nicolaas Govert de Bruijn myntade ordet multiset på 1970-talet, enligt Donald Knuth . Men begreppet multiset föregår myntandet av ordet multiset i många århundraden. Knuth själv tillskriver den första studien av multiset till den indiske matematikern Bhāskarāchārya , som beskrev permutationer av multiset runt 1150. Andra namn har föreslagits eller använts för detta koncept, inklusive lista , bunt , påse , hög , prov , viktad uppsättning , samling och svit .

Historia

Wayne Blizard spårade multiset tillbaka till själva ursprunget för siffror, och hävdade att "i forntida tider representerades numret n ofta av en samling av n streck, talmärken eller enheter." Dessa och liknande samlingar av objekt är multiuppsättningar, eftersom streck, sammanräkningsmärken eller enheter anses vara omöjliga att skilja. Detta visar att människor implicit använde multiset redan innan matematiken dök upp.

Praktiska behov av denna struktur har gjort att multiset har återupptäckts flera gånger och dykt upp i litteraturen under olika namn. Till exempel var de viktiga i tidiga AI- språk, som QA4, där de kallades väskor, en term som tillskrivs Peter Deutsch. En multiset har också kallats en aggregat, heap, bunt, sampel, viktad uppsättning, förekomstuppsättning och fireset (ändligt upprepad elementuppsättning).

Även om multiset användes implicit från urminnes tider, skedde deras explicita utforskning mycket senare. Den första kända studien av multiset tillskrivs den indiske matematikern Bhāskarāchārya omkring 1150, som beskrev permutationer av multiset. Verket av Marius Nizolius (1498–1576) innehåller en annan tidig referens till begreppet multiset. Athanasius Kircher hittade antalet multiset-permutationer när ett element kan upprepas. Jean Prestet publicerade en allmän regel för multiset-permutationer 1675. John Wallis förklarade denna regel mer i detalj 1685.

Richard Dedekinds arbete .

Andra matematiker formaliserade multiset och började studera dem som exakta matematiska strukturer på 1900-talet. Till exempel beskrev Whitney (1933) generaliserade mängder ("mängder" vars karakteristiska funktioner kan ta vilket heltalsvärde som helst - positivt, negativt eller noll). Monro (1987) undersökte kategorin Mul av multiset och deras morfismer , och definierade en multiset som en mängd med en ekvivalensrelation mellan element "av samma sort ", och en morfism mellan multiset som en funktion som respekterar sorter . Han introducerade också ett multital : en funktion f ( x ) från en multiset till de naturliga talen , vilket ger multipliciteten av element x i multiset. Monro hävdade att begreppen multiset och multinumber ofta blandas urskillningslöst, även om båda är användbara.

Exempel

Ett av de enklaste och mest naturliga exemplen är multimängden primtalsfaktorer för ett naturligt tal n . Här är den underliggande uppsättningen element mängden primtalsfaktorer för n . Till exempel har talet 120 primtalsfaktoriseringen

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

vilket ger multisetet {2, 2, 2, 3, 5} .

Ett relaterat exempel är multiuppsättningen av lösningar av en algebraisk ekvation . En andragradsekvation har till exempel två lösningar. Men i vissa fall är de båda lika många. Fleruppsättningen av lösningar av ekvationen kan alltså vara {3, 5} , eller så kan den vara {4, 4} . I det senare fallet har den en lösning av multiplicitet 2. Mer allmänt hävdar algebras grundläggande sats att de komplexa lösningarna av en polynomekvation av grad d alltid bildar en multimängd av kardinalitet d .

Ett specialfall av ovanstående är egenvärdena för en matris , vars multiplicitet vanligtvis definieras som deras multiplicitet som rötter till det karakteristiska polynomet . Men två andra multipliciteter definieras naturligt för egenvärden, deras multipliciteter som rötter till det minimala polynomet och den geometriska multipliciteten , som definieras som dimensionen av kärnan av A − λI (där λ är ett egenvärde av matrisen A ). Dessa tre multipliciteter definierar tre multiuppsättningar av egenvärden, som alla kan vara olika: Låt A vara en n × n matris i jordansk normalform som har ett enda egenvärde. Dess multiplicitet är n , dess multiplicitet som en rot av det minimala polynomet är storleken på det största Jordan-blocket, och dess geometriska multiplicitet är antalet Jordan-block.

Definition

En multiuppsättning kan formellt definieras som ett ordnat par ( A , m ) där A är den underliggande uppsättningen av multiuppsättningen, bildad av dess distinkta element, och $m\colon A\to \mathbb { Z} ^{+}$ är en funktion från A till mängden positiva heltal, vilket ger multipliciteten – det vill säga antalet förekomster – av elementet a i multimängden som talet m ( a ) .

Representerar funktionen m med dess graf (uppsättningen av ordnade par $\left\{\left(a,m\left(a\right)\right) :a\in A\right\}$ ) gör det möjligt att skriva multiset { a , a , b } som ({ a , b }, {( a , 2), ( b , 1)}) , och multiset { a , b } som ({ a , b }, {( a , 1), ( b , 1)}) . Denna notation är dock inte vanligt förekommande och mer kompakta notationer används.

Om $\ldots ,a_{n}\}}$ ( A , m ) ofta som , är en ändlig mängd , representeras multimängden

$\left\{a_{1}^{m(a_{1})},\ldots ,a_{n}^ {m(a_{n})}\right\},\quad$ ibland förenklad till $\quad a_{1}^{m(a_ {1})}\cdots a_{n}^{m(a_{n})},$

där övre index lika med 1 utelämnas. Till exempel kan multiuppsättningen { a , a , b } skrivas $\{a^{2},b\}$ eller $a^{2}b.$ Om elementen i multiuppsättningen är siffror, är en förväxling möjlig med vanliga aritmetiska operationer , de kan normalt uteslutas från sammanhanget. Å andra sidan är den senare notationen förenlig med det faktum att primtalsfaktoriseringen av ett positivt heltal är en unikt definierad multimängd, vilket hävdas av aritmetikens fundamentalsats . En monomial är också en multiuppsättning av obestämda ; till exempel motsvarar monomialen x ³ y ² multiuppsättningen { x , x , x , y , y }.

En multimängd motsvarar en vanlig mängd om multipliciteten för varje element är 1. En indexerad familj ( a _i ) _{i ∈ I} , där i varierar över någon indexmängd I , kan definiera en multimängd, ibland skriven { a _i } . I denna vy ges den underliggande uppsättningen av multiuppsättningen av bilden av familjen, och multipliciteten av alla element x är antalet indexvärden i så att $a_{i}=x$ . I denna artikel anses multipliciteterna vara ändliga, så att inget element förekommer oändligt många gånger i familjen; även i en oändlig multimängd är multipliciteterna ändliga tal.

Det är möjligt att utöka definitionen av en multimängd genom att tillåta multipliciteter av individuella element att vara oändliga kardinaler istället för positiva heltal, men inte alla egenskaper överförs till denna generalisering.

Grundläggande egenskaper och verksamhet

Element i en multimängd tas i allmänhet i en fast uppsättning U , ibland kallad ett universum , som ofta är en uppsättning naturliga tal . Ett element av U som inte tillhör en given multiset sägs ha en multiplicitet 0 i denna multiset. Detta utökar multiplicitetsfunktionen för multimängden till en funktion från U till mängden $\mathbb {N}$ av icke-negativa heltal. Detta definierar en en-till-en-överensstämmelse mellan dessa funktioner och de multiset som har sina element i U .

Denna utökade multiplicitetsfunktion kallas vanligen helt enkelt multiplicitetsfunktionen , och räcker för att definiera multiset när universum som innehåller elementen har fixerats. Denna multiplicitetsfunktion är en generalisering av indikatorfunktionen för en delmängd och delar vissa egenskaper med den.

Stödet för en multiset $A$ i ett universum U är den underliggande uppsättningen av multisetet. Genom att använda multiplicitetsfunktionen $m$ kännetecknas den som

$\operatorname {Supp} (A):=\left\{x\in U\mid m_{A}(x)>0\right\}.$

En multimängd är ändlig om dess stöd är ändligt, eller på motsvarande sätt om dess kardinalitet

$|A|=\summa _{x\i \operatörsnamn {Supp} (A)}m_{A }(x)=\summa _{x\in U}m_{A}(x)$

är ändlig. Den tomma multiuppsättningen är den unika multiuppsättningen med ett tomt stöd (underliggande uppsättning), och därmed en kardinalitet 0.

De vanliga operationerna för uppsättningar kan utökas till multiuppsättningar genom att använda multiplicitetsfunktionen, på ett liknande sätt som att använda indikatorfunktionen för delmängder. I det följande A och B multiuppsättningar i ett givet universum U , med multiplicitetsfunktioner $m_{A}$ och $m_{B}.$

• ( Inkludering: A ingår i B , betecknad A ⊆ B om

$m_{A}(x)\leq m_{B}(x)\quad \forall x\in U.$

• Union : unionen (kallas, i vissa sammanhang, den maximala eller lägsta gemensamma multipeln ) av A och B är multimängden C med multiplicitetsfunktionen

${\displaystyle m_{C}(x)=\max(m_{A}(x),m_{B}(x))\quad \forall x\in U.} Korsning: korsningen ($

• kallas i vissa sammanhang , den infimum eller största gemensamma divisorn ) för A och B är multimängden C med multiplicitetsfunktionen

$)=\min(m_{A}(x),m_{B}(x))\quad \forall x\in U.} Summa$

• x : summan av A och B är multiset C med multiplicitetsfunktion

${\displaystyle m_{C}(x)=m_{A}(x)+m_{B}(x)\quad \forall x\in U.} Det kan ses som en generalisering av den disjunkta föreningen$

av mängder . Den definierar en kommutativ monoid struktur på de finita multiuppsättningarna i ett givet universum. Denna monoid är en fri kommutativ monoid , med universum som bas.

• Skillnad: skillnaden mellan A och B är multimängden C med multiplicitetsfunktion

$m_{C}(x)=\max(m_{A}(x)-m_{B}(x),0)\quad \forall x\in U.$

Två multiuppsättningar är osammanhängande om deras stöd är osammanhängande uppsättningar . Detta motsvarar att säga att deras skärningspunkt är den tomma multimängden eller att deras summa är lika med deras förening.

Det finns en inklusions-exklusionsprincip för finita multimängder (liknande den för mängder ), som säger att en finit union av finita multimängder är skillnaden mellan två summor av multimängder: i den första summan betraktar vi alla möjliga skärningspunkter av ett udda antal av de givna multimängderna, medan vi i den andra summan betraktar alla möjliga skärningspunkter för ett jämnt antal av de givna multimängderna.

Räknar multiset

Bijektion mellan 3-delmängder av en 7-uppsättning (vänster) och 3-multiset med element från en 5-uppsättning (höger) Så detta illustrerar att $\textstyle {7 \choose 3}=\left(\!\!{5 \choose 3}\!\!\right).$

Se även: Stjärnor och staplar (kombinatorik)

Antalet multiset av kardinalitet k , med element hämtade från en ändlig uppsättning av kardinalitet n , kallas multiset koefficient eller multiset nummer . Detta nummer är skrivet av vissa författare som ${\displaystyle \textstyle \left(\!\!{n \choose k}\!\!\right)} ,$ en notation som är tänkt att likna den för binomialkoefficienter ; det används till exempel i (Stanley, 1997) och skulle kunna uttalas " n multichoose k " för att likna " n välj k " för ${\tbinom {n}{k}}.$ Liksom binomialfördelningen som involverar binomialkoefficienter, finns det en negativ binomialfördelning där multisetkoefficienterna förekommer. Multisetkoefficienter ska inte förväxlas med de orelaterade multinomialkoefficienterna som förekommer i multinomsatsen .

Värdet på fleruppsättningskoefficienter kan anges explicit som

$\left(\!\!{n \choose k}\!\!\right)={n+k-1 \choose k}={\frac {(n+k-1)!}{ k!\,(n-1)!}}={n(n+1)(n+2)\cdots (n+k-1) \över k!},$

där det andra uttrycket är som en binomial koefficient; många författare undviker faktiskt separat notation och skriver bara binomialkoefficienter. Så antalet sådana multimängder är detsamma som antalet delmängder av kardinalitet k av en uppsättning av kardinalitet n + k − 1 . Analogin med binomialkoefficienter kan betonas genom att skriva täljaren i uttrycket ovan som en stigande faktoriell potens

$\left(\!\!{n \choose k}\!\!\right)={n^{\overline {k}} \over k!},$

för att matcha uttrycket av binomialkoefficienter med en fallande faktoriell potens:

${n \choose k}={n^{\underline {k}} \över k!}.$

var och en av dem är väldefinierad även om vi tillåter n att vara ett godtyckligt komplext tal.

Det finns till exempel 4 multiset av kardinalitet 3 med element hämtade från mängden {1, 2} av kardinalitet 2 ( n = 2 , k = 3 ), nämligen {1, 1, 1} , {1, 1, 2} , {1, 2, 2} , {2, 2, 2} . Det finns också 4 delmängder av kardinalitet 3 i mängden {1, 2, 3, 4} av kardinalitet 4 ( n + k − 1 ), nämligen {1, 2, 3} , {1, 2, 4} , {1 , 3, 4} , {2, 3, 4} .

Ett enkelt sätt att bevisa likheten mellan multisetkoefficienter och binomialkoefficienter som ges ovan involverar att representera multiset på följande sätt. Tänk först på notationen för multiset som skulle representera a a , a , a , a , a , a , b , b , c , c , c , d , d , d , d , d , d } ( { 6 s, 2 b s, 3 c s, 7 d s) i denna form:

• • • • • • | • • | • • • | • • • • • • •

Detta är en multiuppsättning av kardinalitet k = 18 gjord av element av en uppsättning av kardinalitet n = 4 . Antalet tecken inklusive både punkter och vertikala linjer som används i denna notation är 18 + 4 − 1. Antalet vertikala linjer är 4 − 1. Antalet multiset av kardinalitet 18 är då antalet sätt att ordna 4 − 1 vertikala linjer bland de 18 + 4 − 1 tecknen, och är således antalet delmängder av kardinalitet 4 − 1 av en uppsättning av kardinalitet 18 + 4 − 1. På motsvarande sätt är det antalet sätt att ordna de 18 prickarna bland de 18 + 4 − 1 tecken, vilket är antalet delmängder av kardinalitet 18 av en uppsättning av kardinalitet 18 + 4 − 1. Detta är

${4+18-1 \choose 4-1}={4+18-1 \choose 18}=1330 ,$

sålunda är värdet på multisetkoefficienten och dess ekvivalenser:

$21 \välj 3},$

${\displaystyle \left(\!\!{4 \choose 18}\!\!\right)={21 \choose 18}={\frac {21!}{18!\,3$

$\{stil {röd}{$

$mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10\cdot 11\cdot 12\cdot 13\cdot 14\cdot 15\cdot 16\cdot 17\cdot}} \mathbf {19\cdot 20\cdot 21} }{\mathbf {1\cdot 2\cdot 3} \cdot {\color {röd}{\mathfrak {4\cdot 5\cdot 6\cdot 7\cdot 8\ cdot 9\cdot 10\cdot 11\cdot 12$

$1 3 , {\displaystyle 1 3 = \c t 3 3 . cdot 5\cdots 16\cdot 17\cdot 18\;\mathbf {\cdot \;19\cdot 20\cdot 21} }{\,1\cdot 2\cdot 3\cdot 4\cdot 5\cdots 16\cdot \cdot 18\,\times \,\mathbf {1\cdot 2\cdot 3\quad } }},$

$={\frac {19\cdot 20\cdot 21}{1\cdot 2\cdot 3}}.$

Av relationen mellan binomialkoefficienter och multisetkoefficienter följer att antalet multiset av kardinalitet k i en uppsättning av kardinalitet n kan skrivas

$\left(\!\!{n \choose k}\!\!\right)=(-1)^{k}{-n \choose k}.$

Dessutom,

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

Återkommande förhållande

En återfallsrelation för multisetkoefficienter kan ges som

$\left(\!\!{n \choose k}\!\!\ höger)=\vänster(\!\!{n \välj k-1}\!\!\höger)+\vänster(\!\!{n-1 \välj k}\!\!\höger)\quad {\mbox{för }}n,k>0$

med

$\left(\!\!{n \choose 0}\!\!\right)=1, \quad n\in \mathbb {N} ,\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0 .$

Ovanstående upprepning kan tolkas enligt följande. Låt $[n]:=\{1,\dots ,n\}$ vara källuppsättningen. Det finns alltid exakt en (tom) multiuppsättning av storlek 0, och om n = 0 finns det inga större multiset, vilket ger de initiala förutsättningarna.

Betrakta nu fallet där n , k > 0 . En multiuppsättning av kardinalitet k med element från [ n ] kan eller kanske inte innehåller någon instans av det sista elementet n . Om det visas, då genom att ta bort n en gång, lämnas man med en multiuppsättning av kardinalitet k − 1 av element från [ n ] , och varje sådan multiset kan uppstå, vilket ger totalt

$\left(\!\!{n \choose k-1}\!\!\right)$ möjligheter.

Om n inte visas är vår ursprungliga multimängd lika med en multiuppsättning av kardinalitet k med element från [ n − 1] , av vilka det finns

$\left(\!\!{n-1 \choose k}\!\!\right).$

Således,

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

Genererar serier

Genereringsfunktionen för multisetkoefficienterna är mycket enkel, dvs

$\sum _{d=0}^{\infty }\left(\!\!{n \choose d}\!\!\right)t^{d}={\frac {1}{( 1-t)^{n}}}.$

Eftersom multiset är i en-till-en-överensstämmelse med monomialer , $är {\displaystyle \left(\!\!{n \choose d}\!\!\right)}$ också antalet monomialer för grad d i n obestämd. Ovanstående serie är alltså också Hilbert-serien för polynomringen $k[x_{1},\ldots ,x_{n}].$

Eftersom $\left(\!\!{n \choose d}\!\!\right)$ är ett polynom i n , är det och den genererande funktionen väldefinierade för alla komplexa värden av n .

Generalisering och koppling till den negativa binomialserien

Den multiplikativa formeln tillåter att definitionen av multisetkoefficienter utökas genom att ersätta n med ett godtyckligt tal α (negativt, reellt eller komplext):

$\left(\!\!{\alpha \choose k}\!\!\right)={\frac {\alpha ^{\overline {k}}}{k!}}={\frac { \alpha (\alpha +1)(\alpha +2)\cdots (\alpha +k-1)}{k(k-1)(k-2)\cdots 1}}\quad {\text{för } }k\in \mathbb {N} {\text{ och godtycklig }}\alpha .$

Med denna definition har man en generalisering av den negativa binomialformeln (med en av variablerna satt till 1), vilket motiverar att anropa ( ( $displaystyle \left(\!\!{\alpha \choose k} \!\!\right)}$ negativa binomialkoefficienter:

$(1-X)^{-\alpha }=\summa _{k=0}^{\infty }\left(\!\!{\alpha \choose k}\!\!\right)X ^{k}.$

Denna Taylor-serieformel är giltig för alla komplexa tal α och X med | X | < 1. Det kan också tolkas som en identitet av formella potensserier i X , där det faktiskt kan fungera som definition av godtyckliga potenser av serier med konstant koefficient lika med 1; Poängen är att med denna definition gäller alla identiteter som man förväntar sig för exponentiering , särskilt

$(1-X)^{-\alpha }(1-X)^{-\beta }=(1-X)^{-(\alpha +\beta )}\quad {\text{and} }\quad ((1-X)^{-\alpha })^{-\beta }=(1-X)^{-(-\alpha \beta )}$ ,

och formler som dessa kan användas för att bevisa identiteter för multisetkoefficienterna.

Om α är ett icke-positivt heltal n , så är alla termer med k > − n noll, och den oändliga serien blir en finit summa. Men för andra värden på α , inklusive positiva heltal och rationella tal , är serien oändlig.

Ansökningar

Multiset har olika tillämpningar. De håller på att bli grundläggande inom kombinatorik . Multiset har blivit ett viktigt verktyg i teorin om relationsdatabaser , som ofta använder synonympåsen . Till exempel används ofta multiset för att implementera relationer i databassystem. I synnerhet fungerar en tabell (utan en primärnyckel) som en multiset, eftersom den kan ha flera identiska poster. På liknande sätt SQL på multiset och returnerar identiska poster. Tänk till exempel på "VÄLJ namn från student". Om det finns flera poster med namnet "Sara" i elevtabellen, visas alla. Det betyder att resultatet av en SQL-fråga är en multiset; om resultatet istället var en uppsättning, skulle de repetitiva posterna i resultatuppsättningen ha eliminerats. En annan tillämpning av multiset är vid modellering av multigrafer . I multigrafer kan det finnas flera kanter mellan två givna hörn . Som sådan är enheten som visar kanter en multiset och inte en uppsättning.

Det finns även andra applikationer. Till exempel Richard Rado multiset som en enhet för att undersöka egenskaperna hos familjer av uppsättningar. Han skrev: "Föreställningen om en mängd tar ingen hänsyn till flera förekomster av någon av dess medlemmar, och ändå är det just denna typ av information som ofta är av betydelse. Vi behöver bara tänka på mängden rötter för ett polynom f ( x ) eller spektrumet för en linjär operator ."

Generaliseringar

Olika generaliseringar av multiset har introducerats, studerats och tillämpats för att lösa problem.

• Real-värderade multiset (där multipliciteten av ett element kan vara vilket reellt tal som helst )
• Luddiga multiset
• Grova multiset
• Hybrid set
• stegfunktion med verkligt värde
• Mjuka multiset
• Mjuka fuzzy multiset
• Namngivna uppsättningar (förening av alla generaliseringar av uppsättningar)

Se även

• Frekvens (statistik) som multiplicitetsanalog
• Kvasiuppsättningar
• Mängdlära
• Läromaterial relaterat till partitioner av multiset på Wikiversity