Multiset - Multiset

În matematică , un multiset (sau bag , sau mset ) este o modificare a conceptului de set care, spre deosebire de un set, permite instanțe multiple pentru fiecare dintre elementele sale . Numărul de instanțe dat pentru fiecare element se numește multiplicitatea acelui element în multiset. În consecință, există un număr infinit de multiseturi care conțin doar elemente $a$ și $b$ , dar variază în multiplicitatea elementelor lor:

Mulțimea ${a, b}$ conține doar elemente $a$ și $b$ , fiecare având multiplicitate 1 când ${a, b}$ este văzut ca un multiset.
În multiset ${a, a, b}$ , elementul $a$ are multiplicitate 2 și $b$ are multiplicitate 1.
În multiset ${a, a, a, b, b, b}$ , $a$ și $b$ au ambele multiplicitate 3.

Aceste obiecte sunt toate diferite, atunci când sunt privite ca multiseturi, deși sunt același set , deoarece toate constau din aceleași elemente. La fel ca în cazul mulțimilor și, spre deosebire de tupluri , ordinea nu contează în discriminarea multiseturilor, deci ${a, a, b}$ și ${a, b, a}$ denotă același multiset. Pentru a distinge între mulțimi și multiseturi, se folosește uneori o notație care încorporează paranteze pătrate: multisetul ${a, a, b}$ poate fi notat ca $[a, a, b]$ .

Cardinalitatea unui grup multiplu este construit prin însumarea multiplicitatea tuturor elementelor sale. De exemplu, în multiset ${a, a, b, b, b, c}$ multiplicitățile membrilor $a$ , $b$ și $c$ sunt respectiv 2, 3 și 1 și, prin urmare, cardinalitatea acestui multiset este 6.

Nicolaas Govert de Bruijn a inventat cuvântul multiset în anii 1970, potrivit lui Donald Knuth . Cu toate acestea, utilizarea conceptului de multiseturi precedă inventarea cuvântului multiset de mai multe secole. Knuth însuși atribuie primul studiu al multiseturilor matematicianului indian Bhāskarāchārya , care a descris permutările multiseturilor în jurul anului 1150. Alte nume au fost propuse sau utilizate pentru acest concept, inclusiv listă , grămadă , sac , grămadă , eșantion , set ponderat , colecție și suită .

Istorie

Wayne Blizard a urmărit multiseturile până la originea numerelor, susținând că „în vremurile străvechi, numărul n era adesea reprezentat de o colecție de n linii, semne sau unități”. Aceste colecții și alte colecții similare de obiecte sunt multiseturi, deoarece loviturile, marcajele sau unitățile sunt considerate nedistinguibile. Acest lucru arată că oamenii au folosit implicit multiseturi chiar înainte de apariția matematicii.

Nevoile practice pentru această structură au făcut ca multiseturile să fie redescoperite de mai multe ori, apărând în literatură sub nume diferite. De exemplu, acestea erau importante în limbile AI timpurii, cum ar fi QA4, unde erau denumite genți, un termen atribuit lui Peter Deutsch. Un multiset a fost, de asemenea, numit agregat, heap, grămadă, eșantion, set ponderat, set de apariții și set de incendii (set de elemente repetate finit).

Deși multiseturile au fost utilizate implicit din cele mai vechi timpuri, explorarea lor explicită a avut loc mult mai târziu. Primul studiu cunoscut al multiseturilor este atribuit matematicianului indian Bhāskarāchārya circa 1150, care a descris permutările multiseturilor. Opera lui Marius Nizolius (1498–1576) conține o altă referință timpurie la conceptul de multiseturi. Athanasius Kircher a găsit numărul permutărilor multiset atunci când un element poate fi repetat. Jean Prestet a publicat o regulă generală pentru permutări multiset în 1675. John Wallis a explicat această regulă mai detaliat în 1685.

Multiseturile au apărut explicit în opera lui Richard Dedekind .

Alți matematicieni au formalizat multiseturile și au început să le studieze ca structuri matematice precise în secolul al XX-lea. De exemplu, Whitney (1933) a descris seturi generalizate („seturi” ale căror funcții caracteristice pot lua orice valoare întreagă - pozitivă, negativă sau zero). Monro (1987) a investigat categoria Mul de multiseturi și morfismele lor, definind un multiset ca un set cu o relație de echivalență între elementele „de același fel ” și un morfism între multiseturi ca funcție care respectă sorturile . De asemenea, el a introdus un multinumber : o funcție f ( x ) de la un multiset la numerele naturale , dând multiplicitatea elementului x în multiset. Monro a susținut că conceptele de multiset și multinumber sunt adesea amestecate fără discriminare, deși ambele sunt utile.

Exemple

Unul dintre cele mai simple și mai naturale exemple este multisetul factorilor primi ai unui număr natural $n$ . Aici setul de elemente de bază este ansamblul factorilor primi ai lui $n$ . De exemplu, numărul 120 are factorizarea primă

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

care dă multiset-ul ${2, 2, 2, 3, 5}$ .

Un exemplu înrudit este multiset de soluții ale unei ecuații algebrice. O ecuație pătratică , de exemplu, are două soluții. Cu toate acestea, în unele cazuri, ambele sunt același număr. Astfel, multisetul soluțiilor ecuației ar putea fi ${3, 5}$ sau ar putea fi ${4, 4}$ . În acest din urmă caz are o soluție de multiplicitate 2. Mai general, teorema fundamentală a algebrei afirmă că soluțiile complexe ale unei ecuații polinomiale de grad $d$ formează întotdeauna un multiset de cardinalitate $d$ .

Un caz special din cele de mai sus sunt valorile proprii ale unei matrice , a căror multiplicitate este de obicei definită ca multiplicitatea lor ca rădăcini ale polinomului caracteristic . Cu toate acestea alte două multiplicități sunt definite în mod natural pentru valori proprii, multiplicități lor ca rădăcini ale polinomului minimal , și multiplicitatea geometrică , care este definită ca dimensiunea a nucleului de $A - λI$ (unde $λ$ este o valoare proprie a matricei $A$ ). Aceste trei multiplicități definesc trei multiseturi de valori proprii, care pot fi toate diferite: Fie $A$ fi $n x n$ matrice în formă normală Jordan , care are un singur eigenvalue. Multiplicitatea sa este $n$ , multiplicitatea sa ca rădăcină a polinomului minim este de mărimea celui mai mare bloc Jordan, iar multiplicitatea sa geometrică este numărul de blocuri Jordan.

Definiție

Un multiset poate fi definit formal ca un 2- tuplu $(A, m) în$ care $A$ este setul de bază al multisetului, format din elementele sale distincte, și este o funcție de la $A$ la setul numerelor întregi pozitive , dând multiplicitatea , adică numărul de apariții al elementului $a$ din multiset ca număr $m$ $($ $a$ $)$ . ${\ displaystyle m \ colon A \ to \ mathbb {Z} ^ {+}}$

Reprezentarea funcției $m$ prin graficul său (setul de perechi ordonate ) permite scrierea multisetului ${$ $a$ $,$ $a$ $,$ $b$ $}$ ca $({$ $a$ $,$ $b$ $}, {($ $a$ $, 2), ($ $b$ $, 1)})$ și multiset-ul ${$ $a$ $,$ $b$ $}$ ca $({$ $a$ $,$ $b$ $}, {($ $a$ $, 1), ($ $b$ $, 1)})$ . Cu toate acestea, această notație nu este utilizată în mod obișnuit și sunt folosite notații mai compacte. ${\ displaystyle \ left \ {\ left (a, m \ left (a \ right) \ right): a \ în A \ right \}}$

Dacă este un set finit , multiset-ul $($ $A$ $,$ $m$ $)$ este adesea reprezentat ca ${\ displaystyle A = \ {a_ {1}, \ ldots, a_ {n} \}}$

{\ displaystyle \ left \ {a_ {1} ^ {m (a_ {1})}, \ ldots, a_ {n} ^ {m (a_ {n})} \ right \}, \ quad}

uneori simplificat la

{\ displaystyle \ quad a_ {1} ^ {m (a_ {1})} \ cdots a_ {n} ^ {m (a_ {n})},}

unde indicii superiori egali cu 1 sunt omiși. De exemplu, multisetul { a , a , b } poate fi scris sau Dacă elementele multisetului sunt numere, este posibilă o confuzie cu operațiile aritmetice obișnuite , în mod normal, acestea pot fi excluse din context. Pe de altă parte, ultima notație este coerentă cu faptul că factorizarea primă a unui întreg pozitiv este un multiset definit unic, așa cum se afirmă în teorema fundamentală a aritmeticii . De asemenea, un monom este un multiset de indeterminate ; de exemplu, monomiul x ³y ² corespunde multisetului { x , x , x , y , y }. ${\ displaystyle \ {a ^ {2}, b \}}$ ${\ displaystyle a ^ {2} b.}$

Un multiset corespunde unui set obișnuit dacă multiplicitatea fiecărui element este una (spre deosebire de un număr întreg pozitiv mai mare). O familie indexată , $(a i) i \in I$ , unde $i$ variază în funcție de un set de indici I , poate defini un multiset, uneori scris ${a i}$ . În această vedere, setul de bază al multisetului este dat de imaginea familiei, iar multiplicitatea oricărui element $x$ este numărul de valori ale indexului $i$ astfel încât . În acest articol, multiplicitățile sunt considerate finite, adică niciun element nu apare infinit de multe ori în familie: chiar și într-un multiset infinit, multiplicitățile sunt numere finite. ${\ displaystyle a_ {i} = x}$

Este posibil să se extindă definiția unui multiset permițând multitudinilor de elemente individuale să fie cardinale infinite în loc de numere întregi pozitive, dar nu toate proprietățile trec la această generalizare.

Proprietăți și operațiuni de bază

Elementele unui multiset sunt luate în general într-un set fix $U$ , uneori numit univers , care este adesea setul de numere naturale . Un element din $U$ care nu aparține unui multiset dat se spune că are o multiplicitate 0 în acest multiset. Aceasta extinde funcția de multiplicitate a multisetului la o funcție de la $U$ la setul de numere întregi nenegative . Aceasta definește o corespondență unu-la-unu între aceste funcții și multiseturi care au elementele lor în $U$ . ${\ displaystyle \ mathbb {N}}$

Această funcție de multiplicare extinsă este denumită în mod obișnuit pur și simplu funcția de multiplicare și este suficientă pentru definirea multiseturilor atunci când universul care conține elementele a fost fixat. Această funcție de multiplicitate este o generalizare a funcției indicator a unui subset și împărtășește unele proprietăți cu acesta.

Suportul unui multiset într - un univers $U$ este setul fundamental al multiset. Folosind funcția multiplicitate , este caracterizată ca ${\ displaystyle A}$ ${\ displaystyle m}$

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

.

Un multiset este finit dacă suportul său este finit sau, echivalent, dacă cardinalitatea sa

{\ displaystyle | A | = \ sum _ {x \ in \ operatorname {Supp} (A)} m_ {A} (x) = \ sum _ {x \ in U} m_ {A} (x)}

este finit. Gol MultiSet este Multiset unic cu un gol suport (set suport), și astfel o cardinalitate 0.

Operațiunile obișnuite ale seturilor pot fi extinse la multisets utilizând funcția de multiplicare, în mod similar cu utilizarea funcției indicator pentru subseturi. În cele ce urmează, $A$ și $B$ sunt multiseturi într-un anumit univers $U$ , cu funcții de multiplicitate și ${\ displaystyle m_ {A}}$ ${\ displaystyle m_ {B}.}$

Incluziune: $A$ este inclus în $B$ , notat $A \subseteq B$ , dacă

{\ displaystyle m_ {A} (x) \ leq m_ {B} (x) \ quad \ forall x \ în U.}

Uniunea: unirea (numit, în anumite contexte, maxime sau cel mai mic multiplu comun ) de $A$ și $B$ este MultiSet $C$ cu funcția multiplicitate

{\ displaystyle m_ {C} (x) = \ max (m_ {A} (x), m_ {B} (x)) \ quad \ forall x \ în U.}

Intersecția: intersecția (numită, în anumite contexte, The infimumul sau cel mai mare divizor comun ) a $A$ și $B$ este multiset $C$ cu funcția multiplicitate

{\ displaystyle m_ {C} (x) = \ min (m_ {A} (x), m_ {B} (x)) \ quad \ forall x \ în U.}

Suma: suma dintre $A$ și $B$ este multiset $C$ cu funcția multiplicitate

{\ displaystyle m_ {C} (x) = m_ {A} (x) + m_ {B} (x) \ quad \ forall x \ în U.}

Poate fi privit ca o generalizare a uniunii disjuncte a mulțimilor. Acesta definește o structură monoidică comutativă pe multiseturile finite dintr-un univers dat. Acest monoid este un monoid liber comutativ , având ca bază universul.

Diferență: diferența dintre $A$ și $B$ este multiset $C$ cu funcția multiplicitate

{\ displaystyle m_ {C} (x) = \ max (m_ {A} (x) -m_ {B} (x), 0) \ quad \ forall x \ în U.}

Două seturi multiple sunt disjuncte dacă suporturile lor sunt seturi disjuncte . Acest lucru este echivalent cu a spune că intersecția lor este multisetul gol sau că suma lor este egală cu unirea lor.

Există un principiu de incluziune-excludere pentru multiseturile finite (similar cu cel pentru seturi), afirmând că o uniune finită a multisetelor finite este diferența a două sume de multiseturi: în prima sumă considerăm toate intersecțiile posibile ale unui număr impar de multiseturile date, în timp ce în a doua sumă considerăm toate intersecțiile posibile ale unui număr par al multiseturilor date.

Numărarea multiseturilor

Bijecție între 3-subseturi ale unui set de 7 (stânga)
și 3-multiseturi cu elemente dintr-un set de 5 (dreapta)
Deci, aceasta ilustrează acest lucru .

{\ displaystyle \ textstyle {7 \ choose 3} = \ left (\! \! {5 \ choose 3} \! \! \ right)}

Numărul multiseturilor de cardinalitate $k$ , cu elemente preluate dintr-un set finit de cardinalitate $n$ , se numește coeficientul multiset sau numărul multiset . Acest număr este scris de unii autori ca , o notație care este menită să semene cu cea a coeficienților binomiali ; se folosește de exemplu în (Stanley, 1997) și ar putea fi pronunțat „ $n$ multichoose $k$ ” pentru a semăna cu „ $n$ alege $k$ ” pentru . Spre deosebire de coeficienții binomiali, nu există o „teoremă multiset” în care ar apărea coeficienți multiset și nu ar trebui confundați cu coeficienții multinomiali fără legătură care apar în teorema multinomială . ${\ displaystyle \ textstyle \ left (\! \! {n \ alege k} \! \! \ right)}$ ${\ displaystyle {\ tbinom {n} {k}}}$

Valoarea coeficienților multiset poate fi dată în mod explicit ca

{\ displaystyle \ left (\! \! {n \ alege k} \! \! \ dreapta) = {n + k-1 \ alege k} = {\ frac {(n + k-1)!} {k ! \, (n-1)!}} = {n (n + 1) (n + 2) \ cdots (n + k-1) \ peste k!},}

unde a doua expresie este ca un coeficient binomial; de fapt, mulți autori evită notația separată și scriu doar coeficienți binomiali. Deci, numărul de astfel de multiseturi este același cu numărul de subseturi de cardinalitate $k$ într-un set de cardinalitate $n + k - 1$ . Analogia cu coeficienții binomiali poate fi accentuată scriind numeratorul în expresia de mai sus ca o putere factorială în creștere

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

pentru a se potrivi cu expresia coeficienților binomiali folosind o putere factorială în scădere:

{\ displaystyle {n \ choose k} = {n ^ {\ underline {k}} \ peste k!}.}

Există, de exemplu, 4 multiseturi de cardinalitate 3 cu elemente luate din setul ${1, 2}$ de cardinalitate 2 ( $n = 2$ , $k = 3$ ), și anume ${1, 1, 1}$ , ${1, 1, 2}$ , ${1, 2, 2}$ , ${2, 2, 2}$ . Există, de asemenea, 4 subseturi de cardinalitate 3 în setul ${1, 2, 3, 4}$ al cardinalității 4 ( $n + k - 1$ ), și anume ${1, 2, 3}$ , ${1, 2, 4}$ , ${1 , 3, 4}$ , ${2, 3, 4}$ .

O modalitate simplă de a demonstra egalitatea coeficienților multiset și a coeficienților binomiali menționați mai sus implică reprezentarea multiseturilor în modul următor. În primul rând, luați în considerare notația pentru multiseturi care ar reprezenta ${a, a, a, a, a, a, b, b, c, c, c, d, d, d, d, d, d, d}$ (6 $a$ s, 2 $b$ s, 3 $c$ s, 7 $d$ s) în această formă:

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

Acesta este un multiset de cardinalitate $k$ = 18 format din elemente ale unui set de cardinalitate $n$ = 4. Numărul de caractere, inclusiv puncte și linii verticale utilizate în această notație este 18 + 4 - 1. Numărul de linii verticale este 4 - 1. Numărul multiseturilor de cardinalitate 18 este apoi numărul de moduri de a aranja 4 - 1 linii verticale între cele 18 + 4 - 1 caractere și este astfel numărul de subseturi de cardinalitate 4 - 1 într-un set de cardinalitate 18 + 4 - 1. În mod echivalent, este numărul de moduri de a aranja cele 18 puncte dintre cele 18 + 4 - 1 caractere, care este numărul de subseturi de cardinalitate 18 dintr-un set de cardinalitate 18 + 4 - 1. Acesta este

{\ displaystyle {4 + 18-1 \ alege 4-1} = {4 + 18-1 \ alege 18} = 1330,}

astfel este valoarea coeficientului multiset și a echivalențelor sale:

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

{\ displaystyle = {\ frac {{\ color {red} {\ 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 18}}} \ cdot \ mathbf {19 \ cdot 20 \ cdot 21}} {\ mathbf {1 \ cdot 2 \ cdot 3} \ cdot {\ color {red} {\ 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 18}}}}} ,}

{\ displaystyle = {\ frac {1 \ cdot 2 \ cdot 3 \ cdot 4 \ 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 17 \ cdot 18 \, \ times \, \ mathbf {1 \ cdot 2 \ cdot 3 \ quad}}},}

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

Se poate defini un coeficient binom generalizat

{\ displaystyle {n \ alege k} = {n (n-1) (n-2) \ cdots (n-k + 1) \ peste k!}}

în care $n$ nu este necesar să fie un număr întreg negativ, dar poate fi negativ sau non-întreg sau un număr complex nereal . (Dacă $k$ = 0, atunci valoarea acestui coeficient este 1 deoarece este produsul gol .) Atunci numărul de multiseturi de cardinalitate $k$ într-un set de cardinalitate $n$ este

{\ displaystyle \ left (\! \! {n \ alege k} \! \! \ dreapta) = (- 1) ^ {k} {- n \ alege k}.}

Relația de recurență

O relație de recurență pentru coeficienții multiset poate fi dată ca

{\ displaystyle \ left (\! \! {n \ choose k} \! \! \ right) = \ left (\! \! {n \ choose k-1} \! \! \ right) + \ left ( \! \! {n-1 \ alege k} \! \! \ dreapta) \ quad {\ mbox {pentru}} n, k> 0}

cu

{\ displaystyle \ left (\! \! {n \ alege 0} \! \! \ right) = 1, \ quad n \ in \ mathbb {N}, \ quad {\ mbox {și}} \ quad \ left (\! \! {0 \ choose k} \! \! \ Right) = 0, \ quad k> 0.}

Recurența de mai sus poate fi interpretată după cum urmează. Fie $[n]$ : = setul sursă. Există întotdeauna exact un multiset (gol) de dimensiunea 0, iar dacă $n$ $= 0$ nu există multiseturi mai mari, ceea ce oferă condițiile inițiale. ${\ displaystyle \ {1, \ dots, n \}}$

Acum, ia în considerare cazul în care $n, k > 0$ . Un multiset de cardinalitate $k$ cu elemente din $[n]$ ar putea sau nu să conțină nicio instanță a elementului final $n$ . Dacă apare, atunci eliminând $n$ o dată, rămâne cu un multiset de cardinalitate $k - 1$ de elemente din $[n]$ și poate apărea fiecare astfel de multiset, ceea ce dă un total de

{\ displaystyle \ left (\! \! {n \ alege k-1} \! \! \ right)}

posibilități.

Dacă $n$ nu apare, atunci multiset-ul nostru original este egal cu un multiset de cardinalitate $k$ cu elemente din $[n - 1]$ , dintre care există

{\ displaystyle \ left (\! \! {n-1 \ alege k} \! \! \ right).}

Prin urmare,

{\ displaystyle \ left (\! \! {n \ choose k} \! \! \ right) = \ left (\! \! {n \ choose k-1} \! \! \ right) + \ left ( \! \! {n-1 \ alegeți k} \! \! \ dreapta).}

Generarea de serii

Funcția generatoare a coeficienților multiset este foarte simplă, fiind

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

Deoarece multiseturile sunt în corespondență unu-la-unu cu monomii, este și numărul de monomii de grad $d$ în $n$ nedeterminate. Astfel, seria de mai sus este și seria Hilbert a inelului polinomial ${\ displaystyle \ left (\! \! {n \ alegeți d} \! \! \ right)}$ ${\ displaystyle k [x_ {1}, \ ldots, x_ {n}].}$

Așa cum este un polinom în $n$ , este definit pentru orice valoare complexă a lui $n$ . ${\ displaystyle \ left (\! \! {n \ alegeți d} \! \! \ right)}$

Generalizare și conexiune la seria binomială negativă

Formula multiplicativă permite extinderea definiției coeficienților multiset prin înlocuirea lui n cu un număr arbitrar α (negativ, real, complex):

{\ displaystyle \ 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 {for} } k \ in \ mathbb {N} {\ text {și arbitrar}} \ alpha.}

Cu această definiție se are o generalizare a formei binomiale negative (cu una dintre variabilele setate la 1), ceea ce justifică apelarea coeficienților binomiali negativi: ${\ displaystyle \ left (\! \! {\ alpha \ choose k} \! \! \ right)}$

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

Această formulă din seria Taylor este valabilă pentru toate numerele complexe α și X cu | X | <1. Poate fi interpretat și ca o identitate a seriei formale de putere în X , unde poate servi de fapt ca definiție a puterilor arbitrare ale seriilor cu coeficient constant egal cu 1; punctul este că, cu această definiție, toate identitățile susțin că se așteaptă la exponențiere , în special

{\ displaystyle (1-X) ^ {- \ alpha} (1-X) ^ {- \ beta} = (1-X) ^ {- (\ alpha + \ beta)} \ quad {\ text {și} } \ quad ((1-X) ^ {- \ alpha}) ^ {- \ beta} = (1-X) ^ {- (- \ alpha \ beta)}}

,

și formule precum acestea pot fi utilizate pentru a dovedi identități pentru coeficienții multiset.

Dacă α este un număr întreg nonpositiv n , atunci toți termenii cu k > - n sunt zero, iar seria infinită devine o sumă finită. Cu toate acestea, pentru alte valori ale lui α , inclusiv numere întregi pozitive și numere raționale , seria este infinită.

Aplicații

Multiseturile au diverse aplicații. Acestea devin fundamentale în combinatorică . Multiseturi au devenit un instrument important în teoria bazelor de date relaționale , care utilizează adesea sinonim sac . De exemplu, multisets sunt adesea utilizate pentru a implementa relații în sistemele de baze de date. În special, un tabel (fără o cheie primară) funcționează ca un multiset, deoarece poate avea mai multe înregistrări identice. În mod similar, SQL funcționează pe seturi multiple și returnează înregistrări identice. De exemplu, luați în considerare „SELECTARE nume de la student”. În cazul în care există mai multe înregistrări cu numele „sara” în tabelul studenților, toate acestea sunt afișate. Asta înseamnă că setul de rezultate SQL este multiset. Dacă a fost un set, înregistrările repetitive din setul de rezultate au fost eliminate. O altă aplicație a multisetului este în modelarea multigrafelor . În multigrafele pot exista mai multe muchii între oricare două vârfuri date. Ca atare, entitatea care arată muchiile este un multiset și nu un set.

Există și alte aplicații. De exemplu, Richard Rado a folosit multisets ca dispozitiv pentru a investiga proprietățile familiilor de seturi. El a scris: „Noțiunea de set nu ia în considerare apariția multiplă a vreunui dintre membrii săi și totuși doar acest tip de informație este frecvent de importanță. Trebuie doar să ne gândim la setul de rădăcini ale unui polinom f ( x ) sau spectrul unui operator liniar. "

Generalizări

Diferite generalizări ale multiseturilor au fost introduse, studiate și aplicate la rezolvarea problemelor.

Multisets cu valoare reală (în care multiplicitatea unui element poate fi orice număr real)

Acest lucru pare simplu, deoarece multe definiții pentru seturi fuzzy și multisets sunt foarte asemănătoare și pot fi preluate pentru multisets cu valoare reală doar prin înlocuirea intervalului de valori al funcției caracteristice ([0, 1] sau ℕ = {0, 1, 2 , 3, ...} respectiv) cu ℝ ₀⁺ = [0, ∞). Cu toate acestea, această abordare nu poate fi extins cu ușurință pentru seturile fuzzy generalizate care utilizează un poset sau zăbrele în loc de un grad de simplu membru. Au fost dezvoltate mai multe alte abordări pentru multisets-uri fuzzy care nu au această restricție.

Multiseturi neclare
Multiseturi aspre
Seturi hibride
Multiseturi a căror multiplicitate este orice funcție de pas cu valoare reală
Multiseturi moi
Multiseturi fuzzy moi
Seturi denumite (unificarea tuturor generalizărilor seturilor)

Vezi si

Frecvența (statisticile) ca analog de multiplicitate
Cvasi-seturi
Teoria mulțimilor
Materiale de învățare legate de partițiile multiseturilor la Wikiversity

Referințe

^ Hein, James L. (2003). Matematică discretă . Jones & Bartlett Publishers. pp. 29 –30. ISBN 0-7637-2210-3.
^ ^a ^b ^c Knuth, Donald E. (1998). Algoritmi seminumerici . Arta programării pe calculator . 2 (ed. A 3-a). Addison Wesley . ISBN 0-201-89684-2.
^ Blizard, Wayne D (1989). „Teoria multiset” . Notre Dame Journal of Formal Logic . 30 (1): 36-66. doi : 10.1305 / ndjfl / 1093634995 .
^ ^a ^b ^c ^d ^e Blizard, Wayne D. (1991). „Dezvoltarea teoriei multiset” . Logică modernă . 1 (4): 319-352.
^ Rulifson, JF; Derkson, JA; Waldinger, RJ (noiembrie 1972). QA4: un calcul procedural pentru raționamentul intuitiv (raport tehnic). SRI International. 73.
^ ^a ^b Singh, D .; Ibrahim, AM; Yohanna, T .; Singh, JN (2007). "O prezentare generală a aplicațiilor multiseturilor". Novi Sad Journal of Mathematics . 37 (2): 73-92.
^ Angelelli, I. (1965). „Neînțelegerea de către Leibniz a noțiunii de„ multitudo ”a lui Nizolius ”. Notre Dame Journal of Formal Logic (6): 319-322.
^ Kircher, Athanasius (1650). Musurgia Universalis . Roma: Corbelletti.
^ Prestet, Jean (1675). Elemens des Mathematiques . Paris: André Pralard.
^ Wallis, John (1685). Un tratat de algebră . Londra: John Playford.
^ Dedekind, Richard (1888). A fost sind und was sollen die Zahlen? . Braunschweig: Vieweg.
^ Syropoulos, Apostolos (2001). „Matematica multiseturilor”. În Calude, CS; și colab. (eds.). Procesare multiset: puncte de vedere matematică, informatică și de calcul molecular . Springer-Verlag. pp. 347-358.
^ Whitney, H. (1933). "Funcții caracteristice și algebra logicii". Analele matematicii . 34 : 405–414. doi : 10.2307 / 1968168 .
^ Monro, GP (1987). „Conceptul de multiset”. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171–178. doi : 10.1002 / malq.19870330212 .
^ Syropoulos, Apostolos (2000). „Matematica multiseturilor” . Note de curs în informatică . 2235 : 347-358. doi : 10.1007 / 3-540-45523-X_17 . Adus la 16 februarie 2021 .
^ Aigner, M. (1979). Teoria combinatorie . New York / Berlin: Springer Verlag.
^ Anderson, I. (1987). Combinația seturilor finite . Oxford: Clarendon Press.
^ Stanley, Richard P. (1997). Combinatorie enumerativă . 1 . Cambridge University Press. ISBN 0-521-55309-1.
^ Stanley, Richard P. (1999). Combinatorie enumerativă . 2 . Cambridge University Press. ISBN 0-521-56069-1.
^ Grumbach, S .; Milo, T (1996). „Către algebre tractabile pentru pungi” . Journal of Computer and System Sciences . 52 (3): 570-588. doi : 10.1006 / jcss.1996.0042 .
^ Libkin, L .; Wong, L. (1994). "Unele proprietăți ale limbajelor de interogare pentru genți". Lucrările atelierului privind limbajele de programare a bazelor de date . Springer Verlag. pp. 97–114.
^ Libkin, L .; Wong, L. (1995). „Cu privire la reprezentarea și interogarea informațiilor incomplete în baze de date cu pungi”. Scrisori de prelucrare a informațiilor . 56 (4): 209–214. doi : 10.1016 / 0020-0190 (95) 00154-5 .
^ Blizard, Wayne D. (1989). „Multisets și seturi Fuzzy cu valoare reală”. Seturi și sisteme Fuzzy . 33 : 77–97. doi : 10.1016 / 0165-0114 (89) 90218-2 .
^ Blizard, Wayne D. (1990). „Membru negativ”. Notre Dame Journal of Formal Logic . 31 (1): 346-368.
^ Yager, RR (1986). „Despre teoria pungilor”. Jurnalul internațional de sisteme generale . 13 : 23–37. doi : 10.1080 / 03081078608934952 .
^ Grzymala-Busse, J. (1987). „Învățarea din exemple bazate pe multiseturi brute”. Lucrările celui de-al doilea Simpozion internațional privind metodologiile pentru sistemele inteligente . Charlotte, Carolina de Nord. pp. 325–332.
^ Loeb, D. (1992). "Seturi cu un număr negativ de elemente" . Progrese în matematică . 91 : 64-74. doi : 10.1016 / 0001-8708 (92) 90011-9 .
^ Miyamoto, S. (2001). „Multisets Fuzzy și generalizările lor”. Prelucrare multiset . 2235 : 225–235.
^ Alkhazaleh, S .; Salleh, AR; Hassan, N. (2011). „Teoria Soft Multisets”. Științe matematice aplicate . 5 (72): 3561–3573.
^ Alkhazaleh, S .; Salleh, AR (2012). „Teoria Fuzzy Soft Multiset”. Analiza abstractă și aplicată .
^ Burgin, Mark (1990). „Teoria seturilor numite ca bază fundamentală pentru matematică” . Structuri în teorii matematice . San Sebastian. pp. 417-420.
^ Burgin, Mark (1992). „Despre conceptul de multiset în cibernetică”. Cibernetică și analiză de sistem . 3 : 165–167.
^ Burgin, Mark (2004). „Fundamentele unificate ale matematicii”. arXiv : math / 0403186 .
^ Burgin, Mark (2011). Teoria seturilor numite . Dezvoltări ale cercetării matematice. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

[1] Hein, James L. (2003). Matematică discretă . Jones & Bartlett Publishers. pp. 29 –30. ISBN 0-7637-2210-3.

[Knuth1998-2] Knuth, Donald E. (1998). Algoritmi seminumerici . Arta programării pe calculator . 2 (ed. A 3-a). Addison Wesley . ISBN 0-201-89684-2.

[Blizard1989-3] Blizard, Wayne D (1989). „Teoria multiset” . Notre Dame Journal of Formal Logic . 30 (1): 36-66. doi : 10.1305 / ndjfl / 1093634995 .

[Blizard1991-4] Blizard, Wayne D. (1991). „Dezvoltarea teoriei multiset” . Logică modernă . 1 (4): 319-352.

[Rulifson1972-5] Rulifson, JF; Derkson, JA; Waldinger, RJ (noiembrie 1972). QA4: un calcul procedural pentru raționamentul intuitiv (raport tehnic). SRI International. 73.

[Singh2007-6] Singh, D .; Ibrahim, AM; Yohanna, T .; Singh, JN (2007). "O prezentare generală a aplicațiilor multiseturilor". Novi Sad Journal of Mathematics . 37 (2): 73-92.

[Angelelli1965-7] Angelelli, I. (1965). „Neînțelegerea de către Leibniz a noțiunii de„ multitudo ”a lui Nizolius ”. Notre Dame Journal of Formal Logic (6): 319-322.

[8] Kircher, Athanasius (1650). Musurgia Universalis . Roma: Corbelletti.

[9] Prestet, Jean (1675). Elemens des Mathematiques . Paris: André Pralard.

[10] Wallis, John (1685). Un tratat de algebră . Londra: John Playford.

[11] Dedekind, Richard (1888). A fost sind und was sollen die Zahlen? . Braunschweig: Vieweg.

[12] Syropoulos, Apostolos (2001). „Matematica multiseturilor”. În Calude, CS; și colab. (eds.). Procesare multiset: puncte de vedere matematică, informatică și de calcul molecular . Springer-Verlag. pp. 347-358.

[Whitney-13] Whitney, H. (1933). "Funcții caracteristice și algebra logicii". Analele matematicii . 34 : 405–414. doi : 10.2307 / 1968168 .

[14] Monro, GP (1987). „Conceptul de multiset”. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 33 : 171–178. doi : 10.1002 / malq.19870330212 .

[15] Syropoulos, Apostolos (2000). „Matematica multiseturilor” . Note de curs în informatică . 2235 : 347-358. doi : 10.1007 / 3-540-45523-X_17 . Adus la 16 februarie 2021 .

[Aigner1979-16] Aigner, M. (1979). Teoria combinatorie . New York / Berlin: Springer Verlag.

[Anderson1987-17] Anderson, I. (1987). Combinația seturilor finite . Oxford: Clarendon Press.

[Stanley1997-18] Stanley, Richard P. (1997). Combinatorie enumerativă . 1 . Cambridge University Press. ISBN 0-521-55309-1.

[Stanley1999-19] Stanley, Richard P. (1999). Combinatorie enumerativă . 2 . Cambridge University Press. ISBN 0-521-56069-1.

[GrumbachMilo1996-20] Grumbach, S .; Milo, T (1996). „Către algebre tractabile pentru pungi” . Journal of Computer and System Sciences . 52 (3): 570-588. doi : 10.1006 / jcss.1996.0042 .

[LibkinWong1994-21] Libkin, L .; Wong, L. (1994). "Unele proprietăți ale limbajelor de interogare pentru genți". Lucrările atelierului privind limbajele de programare a bazelor de date . Springer Verlag. pp. 97–114.

[LibkingWong1995-22] Libkin, L .; Wong, L. (1995). „Cu privire la reprezentarea și interogarea informațiilor incomplete în baze de date cu pungi”. Scrisori de prelucrare a informațiilor . 56 (4): 209–214. doi : 10.1016 / 0020-0190 (95) 00154-5 .

[23] Blizard, Wayne D. (1989). „Multisets și seturi Fuzzy cu valoare reală”. Seturi și sisteme Fuzzy . 33 : 77–97. doi : 10.1016 / 0165-0114 (89) 90218-2 .

[Blizard1990-24] Blizard, Wayne D. (1990). „Membru negativ”. Notre Dame Journal of Formal Logic . 31 (1): 346-368.

[Yager1986-25] Yager, RR (1986). „Despre teoria pungilor”. Jurnalul internațional de sisteme generale . 13 : 23–37. doi : 10.1080 / 03081078608934952 .

[Grzymala-Busse1987-26] Grzymala-Busse, J. (1987). „Învățarea din exemple bazate pe multiseturi brute”. Lucrările celui de-al doilea Simpozion internațional privind metodologiile pentru sistemele inteligente . Charlotte, Carolina de Nord. pp. 325–332.

[Loeb1992-27] Loeb, D. (1992). "Seturi cu un număr negativ de elemente" . Progrese în matematică . 91 : 64-74. doi : 10.1016 / 0001-8708 (92) 90011-9 .

[Miyamoto2001-28] Miyamoto, S. (2001). „Multisets Fuzzy și generalizările lor”. Prelucrare multiset . 2235 : 225–235.

[Alkhazaleh2011-29] Alkhazaleh, S .; Salleh, AR; Hassan, N. (2011). „Teoria Soft Multisets”. Științe matematice aplicate . 5 (72): 3561–3573.

[Alkhazaleh2012-30] Alkhazaleh, S .; Salleh, AR (2012). „Teoria Fuzzy Soft Multiset”. Analiza abstractă și aplicată .

[31] Burgin, Mark (1990). „Teoria seturilor numite ca bază fundamentală pentru matematică” . Structuri în teorii matematice . San Sebastian. pp. 417-420.

[32] Burgin, Mark (1992). „Despre conceptul de multiset în cibernetică”. Cibernetică și analiză de sistem . 3 : 165–167.

[33] Burgin, Mark (2004). „Fundamentele unificate ale matematicii”. arXiv : math / 0403186 .

[34] Burgin, Mark (2011). Teoria seturilor numite . Dezvoltări ale cercetării matematice. Nova Science Pub Inc. ISBN 978-1-61122-788-8.

Languages

In other projects