Nel calcolo combinatorio, dati
n
{\displaystyle n}
e
k
{\displaystyle k}
due interi non negativi, si definisce combinazione di un insieme di
n
{\displaystyle n}
elementi presi
k
{\displaystyle k}
alla volta (oppure di classe
k
{\displaystyle k}
, o a
k
{\displaystyle k}
a
k
{\displaystyle k}
) ogni multiinsieme di
k
{\displaystyle k}
elementi che appartengono all'insieme (detti anche "estratti" dall'insieme) di quegli
n
{\displaystyle n}
elementi. Una combinazione è detta semplice, o senza ripetizioni, se e solo se ogni suo membro ha molteplicità 1 (ossia non ci sono elementi che si ripetono), e combinazione con ripetizione altrimenti. Una combinazione semplice di
n
{\displaystyle n}
elementi di classe
k
{\displaystyle k}
è perciò equivalente a un sottoinsieme, di cardinalità
k
{\displaystyle k}
, dell'insieme degli
n
{\displaystyle n}
elementi dai quali è estratta, dunque in tal caso
k
≤
n
{\displaystyle k\leq n}
.
A volte, per questi motivi, se si vuole specificare che una combinazione di
n
{\displaystyle n}
elementi di classe
k
{\displaystyle k}
è una combinazione semplice, viene direttamente chiamata un
k
{\displaystyle k}
-insieme di (un insieme di)
n
{\displaystyle n}
elementi; invece una combinazione con ripetizioni è chiamata un
k
{\displaystyle k}
-multiinsieme di (un insieme di)
n
{\displaystyle n}
elementi.In entrambi i casi, estrazioni di elementi uguali a meno dell'ordine generano comunque la stessa combinazione. Ad esempio, prendendo alcune combinazioni di classe 3 dell'insieme {p,q,r,s,t}, le estrazioni rappresentate dalle terne ordinate (p,r,s), (p,s,r), (r,p,s), (s,p,r), (r,s,p) e (s,r,p) indicano la stessa combinazione in quanto formate dagli stessi elementi, cioè corrispondono tutte all'insieme (non ordinato per definizione) {p,r,s} sottoinsieme di {p,q,r,s,t}. D'altra parte, (p,r,s) e (s,r,q) indicano due diverse combinazioni perché corrispondono agli insiemi {p,r,s} e {s,r,q} che differiscono per almeno un elemento, e l'estrazione (p,p,r,s) identifica una combinazione diversa da (r,p,s,s) perché le molteplicità di p e s differiscono, mentre identifica la stessa combinazione di (p,r,s,p) perché formate dagli stessi elementi con le stesse molteplicità.
View More On Wikipedia.org