Multi-set

Un multiset , în matematică și mai ales în combinatorică , logică matematică și teoria mulțimilor , este o generalizare a conceptului de bază al unui set . Ar putea fi definit cu o listă care admite elemente repetate: de exemplu ar putea fi reprezentată cu o listă ca $la, la, la, b, b, c$ ${\ displaystyle a, a, a, b, b, c}$ ${\ displaystyle a, a, a, b, b, c}$ . O astfel de colecție, de fapt, nu corespunde concepției predominante asupra întregului ca o colecție de elemente care sunt toate distincte unele de altele. Dar în definiția unui multiset, spre deosebire de ceea ce se întâmplă pentru o listă sau o listă, ordinea în care apar elementele nu este relevantă.

În mod formal, un multiset este definit ca o pereche $M=(A,m)$ ${\ displaystyle M = (A, m)}$ ${\ displaystyle M = (A, m)}$ , unde este $LA$ ${\ displaystyle A}$ $LA$ este un set și $m:A\rightarrow \mathbb {N}$ ${\ displaystyle m: A \ rightarrow \ mathbb {N}}$ ${\ displaystyle m: A \ rightarrow \ mathbb {N}}$ este o funcție cu valori naturale pozitive ; A împreună se numește suportul multisetului , elementele sale sunt numite elemente ale multisetului și m multiplicității multisetului . Se poate spune că funcția de multiplicitate asociază fiecărui element al multisetului un număr de repetări care alcătuiesc multisetul însuși; de exemplu în cazul menționat mai sus avem:

$m(a)$ ${\ displaystyle m (a)}$ ${\ displaystyle m (a)}$ = 3
$m(b)$ ${\ displaystyle m (b)}$ ${\ displaystyle m (b)}$ = 2
$m(c)$ ${\ displaystyle m (c)}$ ${\ displaystyle m (c)}$ = 1

Observați că numai funcția multiplicitate identifică complet un set multiplu: de fapt noțiunea poate fi redusă la cea a unei funcții cu valori întregi pozitive și pentru un set multiplu generic, utilizând noțiunea de domeniu , poate fi scrisă $(A,m)=({\mbox{dom}}(m),m)$ ${\ displaystyle (A, m) = ({\ mbox {dom}} (m), m)}$ ${\ displaystyle (A, m) = ({\ mbox {dom}} (m), m)}$ .

Suma numărului de repetări exprimă numărul de perechi care alcătuiesc funcția m și, prin urmare, se numește cardinalitatea multisetului.

Este util să folosiți termenii și notațiile multiseturilor din motive de practică expozitivă, așa cum se întâmplă pentru primele două exemple ale paragrafului următor și în diverse probleme enumerative din combinatorică și teoria grupurilor.

Din cele spuse, este clar că dacă imaginea setată a $m$ ${\ displaystyle m}$ $m$ (adică setul de valori asumate de $m$ ${\ displaystyle m}$ $m$ ) coincide cu întregul $\{1\}$ ${\ displaystyle \ {1 \}}$ ${\ displaystyle \ {1 \}}$ , atunci multi-întregul poate fi confundat cu întregul său suport.

Desigur, deoarece fiecare funcție se poate prezenta ca un set de perechi, fiecare este un set multiplu $M=(A,m)$ ${\ displaystyle M = (A, m)}$ ${\ displaystyle M = (A, m)}$ poate fi prezentat ca setul de perechi ordonate $\{(a,m(a)):a\in A\}$ ${\ displaystyle \ {(a, m (a)): a \ în A \}}$ ${\ displaystyle \ {(a, m (a)): a \ în A \}}$ ; în exemplul inițial: $M=\{(a,3),(b,2),(c,1)\}$ ${\ displaystyle M = \ {(a, 3), (b, 2), (c, 1) \}}$ ${\ displaystyle M = \ {(a, 3), (b, 2), (c, 1) \}}$ .

Numărul de multiseturi de cardinalitate $\ k$ ${\ displaystyle \ k}$ $\ k$ a unui set $\ A$ ${\ displaystyle \ A}$ ${\ displaystyle \ A}$ de cardinalitate $\ n$ ${\ displaystyle \ n}$ $\ n$ Este dat de coeficientul binomial ${k-1 \choose n-1}$ ${\ displaystyle {k-1 \ alegeți n-1}}$ ${\ displaystyle {k-1 \ alegeți n-1}}$ ; este deci egal cu numărul de compoziții ale $\ k$ ${\ displaystyle \ k}$ $\ k$ în $\ n$ ${\ displaystyle \ n}$ $\ n$ a declanșa.

Dacă specificați un univers $\ U$ ${\ displaystyle \ U}$ ${\ displaystyle \ U}$ din care $\ A$ ${\ displaystyle \ A}$ ${\ displaystyle \ A}$ este un subset, definiția funcției de multiplicitate devine $\ m_{u}:U\rightarrow \mathbb {N} _{0}$ ${\ displaystyle \ m_ {u}: U \ rightarrow \ mathbb {N} _ {0}}$ ${\ displaystyle \ m_ {u}: U \ rightarrow \ mathbb {N} _ {0}}$ , din $\ U$ ${\ displaystyle \ U}$ ${\ displaystyle \ U}$ la întreg $\ \mathbb {N} _{0}=\{0,1,2,\dots \}$ ${\ displaystyle \ \ mathbb {N} _ {0} = \ {0,1,2, \ dots \}}$ ${\ displaystyle \ \ mathbb {N} _ {0} = \ {0,1,2, \ dots \}}$ ; în acest caz, multiplicitatea elementelor de $\ U$ ${\ displaystyle \ U}$ ${\ displaystyle \ U}$ care nu aparține $\ A$ ${\ displaystyle \ A}$ ${\ displaystyle \ A}$ Nu-i nimic.

Numărul unor astfel de seturi de cardinalitate $\ k$ ${\ displaystyle \ k}$ $\ k$ a unui set $\ U$ ${\ displaystyle \ U}$ ${\ displaystyle \ U}$ de cardinalitate $\ n$ ${\ displaystyle \ n}$ $\ n$ în terminologia combinatorie clasică se spune numărul de combinații cu repetarea de $\ n$ ${\ displaystyle \ n}$ $\ n$ obiecte de clasă $\ k$ ${\ displaystyle \ k}$ $\ k$ .

Funcția de multiplicitate $\ m_{u}:U\rightarrow \mathbb {N} _{0}$ ${\ displaystyle \ m_ {u}: U \ rightarrow \ mathbb {N} _ {0}}$ ${\ displaystyle \ m_ {u}: U \ rightarrow \ mathbb {N} _ {0}}$ generalizează funcția indicator a unui set, acesta din urmă fiind constrâns să-și asume doar valorile 0 sau 1.

Exemple

Noțiunea de multi-set este utilizată pentru a identifica în mod clar colecția factorilor primi ai unui număr natural dat. De exemplu, dacă observăm asta $720=2^{4}3^{2}5$ ${\ displaystyle 720 = 2 ^ {4} 3 ^ {2} 5}$ ${\ displaystyle 720 = 2 ^ {4} 3 ^ {2} 5}$ , se poate spune că multiplul factorilor primi ai 720 este $A=\{(2,4),(3,2),(5,1)\}$ ${\ displaystyle A = \ {(2,4), (3,2), (5,1) \}}$ ${\ displaystyle A = \ {(2,4), (3,2), (5,1) \}}$ . Un alt exemplu este dat de rădăcinile unui polinom ; de exemplu rădăcinile polinomului $x^{3}-5x^{2}+7x-3$ ${\ displaystyle x ^ {3} -5x ^ {2} + 7x-3}$ ${\ displaystyle x ^ {3} -5x ^ {2} + 7x-3}$ constituie setul multiplu $\{(1,2),(3,1)\}$ ${\ displaystyle \ {(1,2), (3,1) \}}$ ${\ displaystyle \ {(1,2), (3,1) \}}$ .

Trebuie remarcat faptul că în cele două exemple anterioare, vorbind despre seturi multiple, avem afirmații destul de clare și evităm discursurile în care termenul împreună este folosit în mod necorespunzător.

În practică, un set multiplu este adesea identificat în mod eficient cu o notație exponențială care se referă la factorizarea numerelor întregi: pentru exemplul polinomului am putea scrie $\{{\mbox{radici di }}x^{3}-5x^{2}+7x-3\}=1^{2}3^{1}$ ${\ displaystyle \ {{\ mbox {rădăcinile lui}} x ^ {3} -5x ^ {2} + 7x-3 \} = 1 ^ {2} 3 ^ {1}}$ ${\ displaystyle \ {{\ mbox {rădăcinile lui}} x ^ {3} -5x ^ {2} + 7x-3 \} = 1 ^ {2} 3 ^ {1}}$ . De asemenea, pentru această notație, se recomandă evitarea scrierii exponenților egali cu 1. Uneori un set multiplu este prezentat cu o histogramă formată din coloane de pătrate egale suprapuse.

Ne-am putea ocupa și de multiseturi care au drept suport un set infinit: de fapt, o secvență de numere întregi (cum ar fi secvența Fibonacci sau secvența numerelor catalane ) ar putea fi considerată multiset. Cu toate acestea, de obicei, sunt luate în considerare doar multiseturile cu suport finit.

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică