Multiinsieme

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

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 ${\displaystyle 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 ${\displaystyle M=(A,m)}$, dove ${\displaystyle A}$ è un insieme e ${\displaystyle m\colon A\rightarrow \mathbb {N} ^{*}}$ è una funzione a valori naturali positivi; ${\displaystyle A}$ viene detto insieme supporto del multiinsieme, i suoi elementi si dicono elementi del multiinsieme ed ${\displaystyle 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:

• ${\displaystyle m(a)=3,}$
• ${\displaystyle m(b)=2,}$
• ${\displaystyle 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 ${\displaystyle (A,m)=(\mathrm {dom} (m),m)}$.

La somma dei numeri di ripetizioni esprime il numero delle coppie costituenti la funzione ${\displaystyle 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 ${\displaystyle m}$ (ossia l'insieme dei valori assunti da ${\displaystyle m}$) coincide con l'insieme ${\displaystyle \{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 ${\displaystyle M=(A,m)}$ può essere presentato come l'insieme delle coppie ordinate ${\displaystyle \{(a,m(a)):a\in A\}}$; nell'esempio iniziale: ${\displaystyle M=\{(a,3),(b,2),(c,1)\}}$.

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

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

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

La funzione molteplicità ${\displaystyle 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.