Multiinsieme

Un multiinsieme, in matematica, e più in particolare nella combinatoria, nella logica matematica e nella teoria degli insiemi, è una generalizzazione del concetto basilare di insieme. Potrebbe definirsi con un elenco che ammette elementi ripetuti: si potrebbe ad esempio rappresentare con un elenco come $a,a,a,b,b,c$. Una tale collezione, infatti, non corrisponde alla concezione prevalente di insieme come collezione di elementi tutti distinti tra loro. Ma nella definizione di multiinsieme, a differenza di quello che accade per un elenco o una lista, non è rilevante l'ordine in cui compaiono gli elementi.

Formalmente, un multiinsieme è definito come una coppia $M=(A,m)$, dove $A$ è un insieme e $m\colon A\rightarrow \mathbb {N} ^{*}$ è una funzione a valori naturali positivi; $A$ viene detto insieme supporto del multiinsieme, i suoi elementi si dicono elementi del multiinsieme ed $m$ molteplicità del multiinsieme. Si può dire che la funzione molteplicità associa ad ogni elemento del multiinsieme un numero di ripetizioni che costituiscono il multiinsieme stesso; per esempio nel caso sopra menzionato si ha:

• $m(a)=3,$
• $m(b)=2,$
• $m(c)=1.$

Si osservi che la sola funzione molteplicità individua completamente un multiinsieme: in effetti la nozione può ridursi a quella di funzione a valori interi positivi e per un generico multiinsieme, ricorrendo alla nozione di dominio, si può scrivere $(A,m)=(\mathrm {dom} (m),m)$.

La somma dei numeri di ripetizioni esprime il numero delle coppie costituenti la funzione $m$ e quindi viene detta cardinalità del multinsieme.

Risulta utile servirsi dei termini e delle notazioni dei multiinsiemi per ragioni di pratica espositiva, come accade per i due primi esempi del paragrafo che segue e in varie questioni enumerative nella combinatoria e nella teoria dei gruppi.

Da quanto detto si evince in modo esplicito che se l'insieme immagine di $m$ (ossia l'insieme dei valori assunti da $m$) coincide con l'insieme $\{1\}$, allora il multiinsieme si può confondere con il suo insieme sostegno.

Naturalmente, dato che ogni funzione si può presentare come insieme di coppie, ogni multiinsieme $M=(A,m)$ può essere presentato come l'insieme delle coppie ordinate $\{(a,m(a)):a\in A\}$; nell'esempio iniziale: $M=\{(a,3),(b,2),(c,1)\}$.

Il numero dei multinsiemi di cardinalità $k$ di un insieme $A$ di cardinalità $n$ è dato dal coefficiente binomiale ${k-1 \choose n-1}$; è quindi uguale al numero delle composizioni di $k$ in $n$ parti.

Se si specifica un universo $U$ di cui $A$ sia sottoinsieme, la definizione di funzione molteplicità diviene $m_{u}\colon U\rightarrow \mathbb {N}$; in tal caso, la molteplicità degli elementi di $U$ non appartenenti ad $A$ è nulla.

Il numero di tali multinsiemi di cardinalità $k$ di un insieme $U$ di cardinalità $n$ viene detto, nella terminologia combinatoria classica, numero delle combinazioni con ripetizione di $n$ oggetti di classe $k$.

La funzione molteplicità $m_{u}\colon U\rightarrow \mathbb {N}$ generalizza la funzione indicatrice di un insieme, quest'ultima essendo vincolata ad assumere solo i valori 0 o 1.

Esempi

La nozione di multiinsieme serve per individuare con chiarezza la collezione dei fattori primi di un dato numero naturale. Se per esempio si osserva che $720=2^{4}3^{2}5$, si può affermare che il multiinsieme dei fattori primi di 720 è $A=\{(2,4),(3,2),(5,1)\}$. Un altro esempio è dato dalle radici di un polinomio; ad esempio le radici del polinomio $x^{3}-5x^{2}+7x-3$ costituiscono il multiinsieme $\{(1,2),(3,1)\}$.

Si osservi che nei due esempi precedenti, parlando di multiinsiemi si hanno enunciati piuttosto chiari e si evitano discorsi nei quali si usa a sproposito il termine insieme.

Nella pratica spesso un multiinsieme viene efficacemente individuato con una notazione esponenziale che si richiama alla fattorizzazione degli interi: per l'esempio del polinomio si potrebbe scrivere $\{{\text{radici di }}x^{3}-5x^{2}+7x-3\}=1^{2}3^{1}$. Anche per questa notazione si conviene di evitare di scrivere gli esponenti uguali a 1. Talora un multiinsieme viene presentato con un istogramma formato da colonne di quadratini uguali sovrapposti.

Si potrebbero trattare anche multiinsiemi aventi come sostegno un insieme infinito: in effetti una successione di interi (come la successione di Fibonacci o la successione dei numeri di Catalan) potrebbe considerarsi un multiinsieme. Di solito però si considerano solo multiinsiemi con sostegno finito.

Voci correlate

• Combinazione
• Insieme (matematica)
• Funzione indicatrice
• Insieme sfocato
• Lista (informatica)
• ⊍

Collegamenti esterni

• (EN) Eric W. Weisstein, Multiinsieme, su MathWorld, Wolfram Research.