combinazione

Nel calcolo combinatorio, dati e due interi non negativi, si definisce combinazione di un insieme di elementi presi alla volta (oppure di classe , o a a ) ogni multiinsieme di elementi che appartengono all'insieme (detti anche "estratti" dall'insieme) di quegli 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 elementi di classe è perciò equivalente a un sottoinsieme, di cardinalità , dell'insieme degli elementi dai quali è estratta, dunque in tal caso .A volte, per questi motivi, se si vuole specificare che una combinazione di elementi di classe è una combinazione semplice, viene direttamente chiamata un -insieme di (un insieme di) elementi; invece una combinazione con ripetizioni è chiamata un -multiinsieme di (un insieme di) 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à.