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à.

Combinazioni semplici 
Dato un insieme A di cardinalità n, il numero dei sottoinsiemi di A di cardinalità k ≤ n, vale a dire le combinazioni di n elementi presi a k a k, si ottiene dividendo il numero di tutti i possibili sottoinsiemi ordinati di cardinalità k in A (disposizioni di n elementi di classe k) per il numero delle permutazioni di k elementi:

Il simbolo  viene detto coefficiente binomiale.

Giustificazione della formula 
Si considerino i sottoinsiemi di cardinalità 4 dell'insieme {a,b,c,d,e,f}. Avremo che:

Nella fattispecie, i 15 gruppi sono:

abcd, abce, abcf, abde, abdf, abef, acde, 
acdf, acef, adef, bcde, bcdf, bcef, bdef, cdef.

Il risultato può essere ottenuto col seguente ragionamento. Immaginiamo di mettere in un sacchetto le 6 lettere a,b,c,d,e,f ed estraiamo a caso la prima che può essere indifferentemente una delle 6: abbiamo quindi 6 possibilità di estrazione. Ora passiamo ad estrarre la seconda lettera: poiché nel sacchetto ne sono rimaste 5, abbiamo 5 possibilità di estrazione. Passiamo quindi ad estrarre la terza lettera: poiché nel sacchetto ne sono rimaste 4, abbiamo 4 possibilità di estrazione. Infine, reiterando ancora il ragionamento, quando andremo ad estrarre la quarta lettera ne saranno rimaste 3 nel sacchetto e avremo quindi 3 possibilità di estrazione. Se moltiplichiamo tutte le possibilità fra loro, avremo 6×5×4×3 = 360 possibili gruppi.

Il valore ottenuto di 360 è, in realtà, il numero delle disposizioni semplici di 6 oggetti di classe 4 nelle quali l'ordine è rilevante. Ad esempio, le lettere successivamente estratte potrebbero essere a,b,c,d, ma anche d,c,b,a. Le due sequenze rappresentano la stessa combinazione in quanto differiscono solo nell'ordine ma non negli elementi che le costituiscono. In generale, le quattro lettere a,b,c,d possono presentarsi in 24 modi diversi da considerarsi però equivalenti ai fini delle combinazioni:

abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

Non essendo interessati all'ordine di estrazione, dobbiamo dividere 360 per il numero delle sequenze che si possono formare con le stesse 4 lettere, cioè per il numero delle permutazioni di 4 elementi, dato da 4! = 24. Il risultato finale è:

Generalizzando, se abbiamo n elementi da raggruppare a k a k, dobbiamo effettuare il seguente rapporto:

Se moltiplichiamo numeratore e denominatore per (n-k)! otteniamo, come volevasi dimostrare:

Facciamo un ulteriore esempio per ribadire la differenza tra combinazione e disposizione. Se si vuole conoscere il numero di comitati di 3 membri che si possono formare scegliendo tra 6 persone, interessa solo sapere in quanti modi si possono scegliere i membri del comitato indipendentemente da chi venga scelto per primo o per ultimo: in tal caso stiamo considerando le combinazioni e il numero dei comitati possibili è dato da C6,3 = 20. Se invece volessimo sapere in quanti modi possono presentarsi i primi 3 classificati tra 6 concorrenti, l'ordine sarebbe rilevante: in quest'altro caso stiamo considerando le disposizioni e quindi le possibili classifiche sarebbero date da D6,3 = 120.

Ordine lessicografico 
Al fine di evitare di considerare erroneamente come valida una combinazione semplice che in realtà è già stata precedentemente presa in considerazione con un altro ordine, si può ricorrere a quest'altra definizione di combinazione.

Si consideri un insieme S di n elementi, preventivamente ordinati e si consideri un intero naturale k tale che 0≤k≤n. Si dice combinazione di elementi di S di lunghezza k ogni sequenza di k elementi di S che sia crescente in base all'ordine preventivamente prefissato.

Ad esempio, le combinazioni di lunghezza 4 degli elementi di {a,b,c,d,e,f}, preventivamente ordinati secondo il tradizionale ordine alfabetico, sono le seguenti 15:

abcd abce abcf abde abdf abef acde acdf acef adef
bcde bcdf bcef bdef
cdef

Si può notare come le combinazioni rispettino l'ordine lessicografico, in conformità con l'ultima definizione data. Attenendosi all'ordine, si evita di fare confusione considerando come diverse due combinazioni che in realtà non lo sono, tratti in inganno dall'ordine diverso con il quale si presentano i suoi elementi.

Criptomorfismo 
Rifacendoci all'esempio di prima, si possono codificare le combinazioni semplici che abbiamo ottenuto con delle sequenze binarie. Nel nostro caso particolare tali sequenze binarie sono di lunghezza 6 e peso 4 e presentano lo stesso contenuto informativo delle combinazioni indicate nell'esempio. Nella fattispecie, usando numeri binari di 6 cifre, di cui la prima sia 1 se compare la a e zero in caso contrario, la seconda sia 1 o 0 secondo che compaia o meno la b ecc., abbiamo:

111100 111010 111001 110110 110101 110011 101110 101101 101011 100111
011110 011101 011011 010111
001111

Si noti come queste sequenze siano presentate in ordine antilessicografico.

In generale, quindi, tra le combinazioni semplici di n elementi di lunghezza k e le sequenze binarie di lunghezza n e peso k si ha un criptomorfismo e risulta equivalente operare con le combinazioni o con le sequenze binarie. Poter operare in modo equivalente con le sequenze binarie si rivela molto utile in ambito informatico.

Combinazioni con ripetizione 
Nelle combinazioni con ripetizione di lunghezza k, ogni elemento può essere ripetuto fino a k volte.
Il loro numero è:

Tale risultato può essere dimostrato in diversi modi.

Prima dimostrazione 
Dato un qualsiasi insieme finito di n elementi, questo può essere posto in corrispondenza biunivoca con l'insieme {1, 2, ... , n}.

Per calcolare  si considerano le sequenze non decrescenti, di lunghezza k, di interi appartenenti a {1, 2, ... , n}. Consideriamo una di queste sequenze:

e associamole la sequenza:

La nuova sequenza è strettamente crescente, non presenta ripetizioni e quindi individua una combinazione semplice di lunghezza k degli interi in {1, 2, ... , n+k–1}. La precedente associazione pone in corrispondenza biunivoca le combinazioni con ripetizioni di lunghezza k degli elementi di {1, 2, ... , n} con le combinazioni semplici di lunghezza k degli interi in {1, 2, ... , n+k-1}. Quindi il numero delle combinazioni con ripetizioni di lunghezza k dei primi n interi positivi coincide con il numero delle combinazioni semplici di lunghezza k dei primi n+k-1 interi positivi:

Un esempio può aiutare a comprendere meglio la dimostrazione. Dato l'insieme {1,2}, associamo a ciascuna delle sue combinazioni con ripetizione di classe 3 una sequenza definita come sopra:

1,1,1 → 1, 1+1, 1+2 → 1,2,3
1,1,2 → 1, 1+1, 2+2 → 1,2,4
1,2,2 → 1, 2+1, 2+2 → 1,3,4
2,2,2 → 2, 2+1, 2+2 → 2,3,4

A ciascuna delle combinazioni con ripetizione corrisponde una ed una sola delle combinazioni semplici di classe 3 dell'insieme {1, ... , (2+3-1)} = {1, 2, 3, 4} e viceversa. Il numero delle prime è quindi uguale al numero delle seconde, che è C2+3–1,3.

Seconda dimostrazione 
Il numero delle combinazioni di n elementi di classe k è uguale al numero delle funzioni crescenti da un insieme A di cardinalità k in un insieme B di cardinalità n.

Una qualsiasi di tali funzioni è un insieme di coppie (ai,bj), in cui ai è un elemento di A (con i = 1,2,...,k) e bj è un elemento di B (con j = 1,2,...,n). In tale insieme, vi sono tante coppie quanti sono gli elementi di A e nessun elemento di A compare in più di una coppia. Gli elementi di B, inoltre, possono ciascuno comparire in nessuna o più coppie.

Si considerano rilevanti, in una prima fase, le sequenze di coppie; ad esempio, individuate due coppie in cui sia presente al secondo membro un dato elemento b, la sequenza (a1, b), (a2, b) è diversa dalla sequenza (a2, b), (a1, b).

Si indicano inoltre con Fk l'insieme delle funzioni da A in B, con Fk-1 l'insieme delle funzioni da un sottoinsieme di cardinalità k–1 di A in B, in entrambi i casi considerando distinte, provvisoriamente, funzioni diverse solo per la sequenza delle coppie che condividono il secondo membro.

Sia |Fk-1| il numero delle funzioni dell'ultimo tipo. Vi sono n+k–1 modi di estendere ciascuna di tali funzioni a tutto A. Infatti, scelto un qualsiasi elemento bj di B, se questo è già presente in altre mj coppie (quelle, appunto, il cui secondo membro è bj), la nuova coppia (ak, bj) potrà essere posta in sequenza con le altre in mj+1 modi diversi: prima della prima, oppure dopo una qualsiasi delle m. Considerando che:

e che la nuova coppia può avere al secondo membro un qualsiasi elemento di B, si ha:

La cardinalità dell'insieme Fk può quindi essere calcolata per ricorrenza:

Si può osservare che si tratta del numero di disposizioni semplici di (n+k–1) elementi di classe k.

Per ottenere il numero delle funzioni crescenti, è sufficiente eliminare la distinzione prima introdotta tra funzioni diverse solo per la sequenza delle coppie, quindi scegliere una sola delle k! permutazioni delle coppie (che sono tante quante gli elementi di A). Si ottiene così:

Anche qui può essere utile un esempio. Siano A = {a1,a2,a3} e B = {b1,b2}. L'insieme F1 contiene solo due funzioni: (a1,b1) e (a1,b2).

Aggiungiamo ora le coppie che hanno a2 come primo elemento e consideriamo distinte le funzioni con diverse sequenze delle coppie che condividono il secondo membro. Otteniamo le funzioni in F2:

Si ha quindi:

Si tratta delle 6 disposizioni semplici di (2+2-1) = 3 elementi di classe 2. I tre elementi sono i due elementi di A finora considerati ed un "elemento di separazione" che consenta di distinguere quali sono associati a b1 e quali a b2. Indicando tale elemento con una barra verticale, le sei funzioni sono:

 a1 a2 |     (entrambi associati a b1)
 a2 a1 |     (entrambi associati a b1)
 a1 | a2     (a1 associato a b1, a2 associato a b2)
 a2 | a1     (a2 associato a b1, a1 associato a b2)
 | a1 a2     (entrambi associati a b2)
 | a2 a1     (entrambi associati a b2)

Per ottenere il numero delle funzioni crescenti, quelle cioè tali che se i < j allora f(ai) ≤ f(aj), basta dividere per il numero delle permutazioni dei due elementi di A, che sono 2! = 2. Si ottiene così che le funzioni crescenti sono 6/2 = 3 (sono quelle al primo, terzo e quinto posto dell'elenco).

Per estendere le funzioni a tutto A, aggiungiamo le coppie che hanno a3 come primo elemento:

per un totale di 24 coppie. Si ha quindi:

Questo è il numero delle disposizioni semplici di (2+3-1) = 4 elementi di classe 3, dove i quattro elementi sono a1, a2, a3 e l'"elemento separatore" che consente di distinguere se sono associati a b1 oppure a b2. Il numero delle funzioni crescenti si ottiene dividendo per il numero delle permutazioni dei tre elementi di A: 24/3! = 24/6 = 4. Le funzioni crescenti sono, infatti:
 a1 a2 a3 |    ovvero    (a1,b1),(a2,b1),(a3,b1)
 a1 a2 | a3    ovvero    (a1,b1),(a2,b1),(a3,b2)
 a1 | a2 a3    ovvero    (a1,b1),(a2,b2),(a3,b2)
 | a1 a2 a3    ovvero    (a1,b2),(a2,b2),(a3,b2)

Terza dimostrazione 
La precedente dimostrazione può essere semplificata come segue. Dato un insieme A di k elementi, vogliamo ripartire i suoi elementi in n gruppi, ciascuno contenente da 0 a k elementi di A. Rappresentiamo gli elementi di A con asterischi, i gruppi con n–1 barre verticali; ad esempio, se n = 4 e k = 6, possiamo avere ripartizioni come le seguenti (tra parentesi il numero di elementi in ciascun gruppo):

 ∗ ∗ | ∗ ∗ | ∗ | ∗      (2,2,1,1)
 |  ∗ ∗ ∗ | ∗ | ∗ ∗      (0,3,1,2)

oppure:

 ∗ ∗ | | | ∗ ∗ ∗ ∗      (2,0,0,4)

o anche:

 ∗ ∗ ∗ ∗ ∗ ∗ | | |      (6,0,0,0)

In ciascuna rappresentazione abbiamo una sequenza di n+k–1 simboli. Dal momento che non interessa l'ordine, si tratta solo di vedere in quanti modi si possono scegliere n–1 di tali simboli per farne delle barre. In altre parole, si tratta di trovare tutte le possibili permutazioni di n+k–1 simboli, considerando che k sono uguali tra loro (gli asterischi) e lo stesso vale per le n–1 barre verticali. Si ha quindi, per una proprietà del coefficiente binomiale e tenendo conto della formula per permutazioni con ripetizioni:

Esempi 
Le combinazioni con ripetizione di lunghezza 2 dei primi 5 interi positivi sono:

e precisamente: 11, 12, 13, 14, 15, 22, 23, 24, 25, 33, 34, 35, 44, 45, 55.

Si può però anche avere k > n: ad esempio, le combinazioni di lunghezza 5 dei primi 2 interi positivi sono:

ossia: 11111, 11112, 11122, 11222, 12222, 22222.

Numero di soluzioni intere di un'equazione 
Il calcolo delle combinazioni con ripetizione consente di trovare il numero delle soluzioni intere non negative di un'equazione in n variabili del tipo:

In questo caso k può essere visto come il numero delle unità che si possono ripartire in n gruppi diversi, anche vuoti, quindi come il numero degli asterischi della terza dimostrazione, svolgendo i "+" il ruolo delle barre. Ad esempio, l'equazione:

ammette, tra le altre, le seguenti soluzioni (tra parentesi la rappresentazioni con sequenze di "1" e "+"):

Trovare il loro numero equivale a trovare il numero delle combinazioni con ripetizione di n elementi di classe k. Nel caso dell'equazione data, il numero è:

Per un caso più semplice, le soluzioni intere non negative dell'equazione

sono:

ossia le quattro coppie (0,3), (1,2), (2,1), (3,0).

Si può anche calcolare il numero delle soluzioni intere positive di un'equazione (detto "numero delle composizioni di k in n parti"). Data un'equazione del tipo:

basta trasformarla in:

ponendo yi = xi–1. Si ottiene così:

Nel caso dell'equazione x1+x2 = 3, il numero delle soluzioni intere positive (il numero delle composizioni di 3 in 2 parti) è:

ossia le due coppie (1,2) e (2,1).

Multiinsiemi 
Il numero delle combinazioni con ripetizione di n elementi di classe k è il numero dei multiinsiemi di cardinalità k con sostegno un insieme di cardinalità n.

Si usa, al riguardo, la definizione di multiinsieme come funzione mU: U → {0,1,2,...}. Ad esempio, dato l'insieme U = {a,b,c}, un multiinsieme di cardinalità 3 è {(a,0), (b,2), (c,1)}, ossia, nella notazione esponenziale, a0 b2 c1. La sua cardinalità è la somma dei secondi membri delle coppie, o degli esponenti nella seconda notazione. Tale multiinsieme può essere rappresentato come una delle possibili combinazioni con ripetizione di classe 3 dei 3 elementi di U: bbc.

Il numero delle combinazioni con ripetizione di classe 3 dei 3 elementi di U è (3+3–1)!/(2!3!) = 10; le combinazioni sono:

aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc.

Questo è anche il numero dei multiinsiemi di cardinalità 3 di U, che sono:

a3b0c0, a2b1c0, a2b0c1, a1b2c0, a1b1c1, a1b0c2, a0b3c0, a0b2c1, a0b1c2, a0b0c3

Si può notare che il loro numero è anche uguale a quello delle soluzioni intere non negative dell'equazione:

Note

Bibliografia 
 Mauro Cerasoli, Franco Eugeni e Marco Protasi, Elementi di matematica discreta, Zanichelli, Bologna, 1988.
 Sheldon M. Ross, Calcolo delle probabilità, Apogeo, Milano, 2004.

Voci correlate 
 Calcolo combinatorio
 Disposizione
 Multinsieme
 Permutazione
 Reticolo booleano
 Triangolo di Tartaglia

Altri progetti

Collegamenti esterni 
 
 
 Se lancio più dadi, qual è la probabilità di ottenere una certa somma? Un'applicazione delle combinazioni con ripetizione al lancio di più dadi

Combinatoria