Combinazione

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.
bussola Disambiguazione – Se stai cercando altri significati, vedi Combinazione (disambigua).

Nel calcolo combinatorio, se n e k sono due interi positivi, si definisce combinazione di n elementi presi k alla volta (oppure di n elementi di classe k) ogni sottoinsieme di k oggetti estratti da un insieme di n oggetti. Se si impone la condizione che una combinazione non può avere un elemento ripetuto si parla di combinazioni semplici, altrimenti di combinazioni con ripetizione. Nel primo caso deve essere ovviamente kn.

In entrambi i casi i sottoinsiemi si considerano indipendenti dall'ordine degli elementi. Ad esempio, se siamo in presenza dell'insieme {p,q,r,s,t} e prendiamo in esame le combinazioni di classe 3, non fa alcuna differenza considerare i gruppi prs, psr, rps, spr, rsp ed srp in quanto essi sono formati dagli stessi elementi, mentre prs ed srq sono considerate due combinazioni distinte in quanto differiscono in alcuni degli elementi.

Combinazioni semplici[modifica | modifica sorgente]

Dato un insieme A di cardinalità n, il numero dei sottoinsiemi di A di cardinalità kn si ottiene calcolando prima il numero delle funzioni da un generico sottoinsieme di cardinalità k in A, che è il numero delle disposizioni di n elementi di classe k, poi, dal momento che si prescinde dall'ordine, si divide tale numero per quello delle permutazioni di k elementi:

C_{n,k}=\frac{D_{n,k}}{P_k}=\frac{n!}{(n-k)!k!}={n \choose k}

Il simbolo {n \choose k} viene detto coefficiente binomiale.

Giustificazione della formula[modifica | modifica sorgente]

Facciamo riferimento al numero dei sottoinsiemi di cardinalità 4 dell'insieme {a,b,c,d,e,f}; per la definizione data, abbiamo:

C_{6,4}=\frac{6!}{(6-4)!4!}=\frac{6!}{2!4!}=\frac{720}{2\cdot 24}=15

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. A questo punto nel sacchetto ne sono rimaste 4: quando estrarremo la terza lettera avremo 4 possibilità di estrazione. Infine, essendone rimaste 3, quando estrarremo la quarta lettera avremo 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 differiscono nell'ordine, ma comprendono entrambe gli stessi elementi di un unico sottoinsieme dell'insieme dato. 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

Poiché nelle combinazioni non siamo interessati all'ordine di estrazione, dobbiamo dividere 360 per il numero di tutte le diverse 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 è:

 
C_{6, 4} = \frac{D_{6,4}}{P_4}=\frac {6 \cdot 5 \cdot  4 \cdot  3} {4 \cdot  3 \cdot  2 \cdot  1} = \frac {6 \cdot 5 \cdot  4 \cdot  3} {4!} = \frac {360} {24} = 15

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

 
C_{n, k} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1)} {k (k-1) (k-2) \cdot\cdot\cdot 1} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1)} {k!}

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

 
C_{n, k} = \frac {n (n-1) (n-2) \cdot\cdot\cdot (n-k+1) (n-k)!} {k! (n-k)!} = \frac {n!} {k! (n-k)!}

Ad esempio, 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 e non importa quale venga scelto per primo o quale per ultimo: in tal caso, il numero dei comitati possibili è C6,3 = 20. Se invece volessimo sapere in quanti modi possono presentarsi i primi 3 classificati tra 6 concorrenti, l'ordine sarebbe rilevante e, quindi, le possibili classifiche sarebbero D6,3 = 120.

Ordine lessicografico[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

C'_{n,k} = C_{n+k-1,k} = {n + k -1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}

Tale risultato può essere dimostrato in diversi modi.

Prima dimostrazione[modifica | modifica sorgente]

Dato un qualsiasi insieme finito di n elementi, questo può essere posto in corrispondenza biunivoca con l'insieme {1, 2, ... , n}; ci si può quindi chiedere quanti sono i sottoinsiemi di cardinalità k di questo.

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

m_1,m_2,\dots,m_k

e associamole la sequenza:

m_1,m_2+1,\dots,m_k+k-1

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:

C'_{n,k} = C_{n+k-1,k} = {n + k -1 \choose k} = \frac{(n+k-1)!}{(n-1)!k!}

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[modifica | modifica sorgente]

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 a 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:

m_1+m_2+\cdots+m_n=k-1

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

(m_1+1)+(m_2+1)+\cdots+(m_n+1)=n+k-1

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

\begin{align}|F_k|&=(n+k-1)|F_{k-1}=\\&=(n+k-1)(n+k-2)\cdots(n+1)|F_1|=\\&=(n+k-1)(n+k-2)\cdots(n+1)n=\\&=\frac{(n+k-1)!}{(n-1)!}\end{align}

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ì:

C'_{n,k}=\frac{(n+k-1)!}{(n-1)!k!}={n+k-1 \choose k}

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:

da (a1,b1)      da (a1,b2)
(a2,b1), (a1,b1) (a2,b1), (a1,b2)
(a1,b1), (a2,b1) (a2,b2), (a1,b2)
(a1,b1), (a2,b2) (a1,b2), (a2,b2)

Si ha quindi:

\begin{align}F_1 &= n = 2\\F_2 &= (n+1)F_1= (2+1)\cdot2 = 6\end{align}

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:

  1. a1 a2 |     (entrambi associati a b1)
  2. a2 a1 |     (entrambi associati a b1)
  3. a1 | a2     (a1 associato a b1, a2 associato a b2)
  4. a2 | a1     (a2 associato a b1, a1 associato a b2)
  5. | a1 a2     (entrambi associati a b2)
  6. | 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:

da (a2,b1), (a1,b1) da (a1,b1), (a2,b1) da (a1,b1), (a2,b2) da (a2,b1), (a1,b2) da (a2,b2), (a1,b2) da (a1,b2), (a2,b2)
(a3,b1),(a2,b1),(a1,b1) (a3,b1),(a1,b1),(a2,b1) (a3,b1),(a1,b1),(a2,b2) (a3,b1),(a2,b1),(a1,b2) (a3,b1),(a2,b2),(a1,b2) (a3,b1),(a1,b2),(a2,b2)
(a2,b1),(a3,b1),(a1,b1) (a1,b1),(a3,b1),(a2,b1) (a1,b1),(a3,b1),(a2,b2) (a2,b1),(a3,b1),(a1,b2) (a3,b2),(a2,b2),(a1,b2) (a3,b2),(a1,b2),(a2,b2)
(a2,b1),(a1,b1),(a3,b1) (a1,b1),(a2,b1),(a3,b1) (a1,b1),(a3,b2),(a2,b2) (a2,b1),(a3,b2),(a1,b2) (a2,b2),(a3,b2),(a1,b2) (a1,b2),(a3,b2),(a2,b2)
(a2,b1),(a1,b1),(a3,b2) (a1,b1),(a2,b1),(a3,b2) (a1,b1),(a2,b2),(a3,b2) (a2,b1),(a1,b2),(a3,b2) (a2,b2),(a1,b2),(a3,b2) (a1,b2),(a2,b2),(a3,b2)

per un totale di 24 coppie. Si ha quindi:

F_3 = (n+k-1)F_2 = (2+3-1)\cdot 6= 24

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:

  1. a1 a2 a3 |    ovvero    (a1,b1),(a2,b1),(a3,b1)
  2. a1 a2 | a3    ovvero    (a1,b1),(a2,b1),(a3,b2)
  3. a1 | a2 a3    ovvero    (a1,b1),(a2,b2),(a3,b2)
  4. | a1 a2 a3    ovvero    (a1,b2),(a2,b2),(a3,b2)

Terza dimostrazione[modifica | modifica sorgente]

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:

C'_{n,k}={n+k-1 \choose n-1}={n+k-1 \choose (n+k-1)-(n-1)}={n+k-1 \choose k}

Esempi[modifica | modifica sorgente]

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

C'_{5,2}={5+2-1 \choose 2} = \frac{6!}{4!2!} = 15

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:

C'_{2,5}={2+5-1 \choose 5} = \frac{6!}{1!5!} = 6

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

Numero di soluzioni intere di un'equazione[modifica | modifica sorgente]

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

x_1+x_2+\cdots+x_n=k

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:

x_1+x_2+x_3+x_4 = 6

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

x_1=2, x_2=2, x_3=1, x_4=1\qquad(11+11+1+1)
x_1=0, x_2=3, x_3=1, x_4=2\qquad(+111+1+11)
x_1=2, x_2=0, x_3=0, x_4=4\qquad(11+++1111)
x_1=6, x_2=0, x_3=0, x_4=0\qquad(111111+++)

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 è:

C'_{4,6}={4+6-1 \choose 4-1}={4+6-1 \choose 6}=84

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

x_1+x_2=3

sono:

C'_{2,3}={2+3-1 \choose 2-1}={2+3-1 \choose 3}=4

ovvero 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:

x_1+x_2+\cdots+x_n=k

basta trasformarla in:

y_1+y_2+\cdots+y_n=k-n

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

{n+(k-n)-1 \choose n-1}={k-1 \choose n-1}

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

{3-1 \choose 2-1}={2 \choose 1}=2

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

Multinsiemi[modifica | modifica sorgente]

Il numero delle combinazioni con ripetizione di n elementi di classe k viene anche detto numero dei multinsiemi di cardinalità k di un insieme di cardinalità n.

Si usa, al riguardo, la definizione di multinsieme come funzione mU: U → {0,1,2,...}. Ad esempio, dato l'insieme U = {a,b,c}, un multinsieme di cardinalità 3 è {(a,0), (b,2), (c,1)}, ovvero, nella notazione esponenziale, a0 b2 c1. La sua cardinalità è la somma dei secondi membri delle coppie, o degli esponenti nella seconda notazione. Tale multinsieme 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 multinsiemi 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:

x_1+x_2+x_3=3

Bibliografia[modifica | modifica sorgente]

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

Voci correlate[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica