Combinazione: differenze tra le versioni

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Contenuto cancellato Contenuto aggiunto
Botcrux (discussione | contributi)
m Bot: sposto {{collegamenti esterni}} in cima alla sezione (cfr. manuale)
Rightaway2 (discussione | contributi)
Nessun oggetto della modifica
Riga 2: Riga 2:
{{Nota disambigua}}
{{Nota disambigua}}


Nel [[calcolo combinatorio]], se ''n'' e ''k'' sono due [[Numero intero|interi]] positivi, si definisce '''combinazione''' di ''n'' elementi presi ''k'' alla volta (oppure di ''n'' elementi di classe ''k'' oppure di ''n'' elementi a ''k'' a ''k'') ogni sottoinsieme di ''k'' elementi estratti da un insieme di ''n'' elementi. Si parlerà di '''combinazione semplice''' se essa non può avere elementi che si ripetono e di [[combinazioni con ripetizione|combinazione con ripetizione]] altrimenti. Nel caso di combinazioni semplici deve risultare necessariamente ''k'' ≤ ''n''.
Si definisce '''combinazione''' di ''n'' elementi presi ''k'' alla volta (oppure di ''n'' elementi di classe ''k'' oppure di ''n'' elementi a ''k'' a ''k'') ogni sottoinsieme di ''k'' elementi estratti da un insieme di ''n'' elementi.
E' utilizzata nel [[calcolo combinatorio]], se ''n'' e ''k'' sono due [[Numero intero|interi]] positivi. Si parla di '''combinazione semplice''' se essa non può avere elementi che si ripetono e di [[combinazioni con ripetizione|combinazione con ripetizione]] altrimenti. Nel caso di combinazioni semplici deve risultare necessariamente ''k'' ≤ ''n''.


In entrambi i casi i sottoinsiemi vanno considerati '''indipendentemente 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, i gruppi ''prs'', ''psr'', ''rps'', ''spr'', ''rsp'' ed ''srp'' rappresentano ''la stessa combinazione'' in quanto formati dagli stessi elementi mentre i gruppi ''prs'' ed ''srq'' rappresentano ''due diverse combinazioni'' in quanto differiscono in almeno uno degli elementi.
In entrambi i casi i sottoinsiemi vanno considerati '''indipendentemente 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, i gruppi ''prs'', ''psr'', ''rps'', ''spr'', ''rsp'' ed ''srp'' rappresentano ''la stessa combinazione'' in quanto formati dagli stessi elementi mentre i gruppi ''prs'' ed ''srq'' rappresentano ''due diverse combinazioni'' in quanto differiscono in almeno uno degli elementi.

Versione delle 13:30, 1 apr 2019

Template:Avvisounicode

Disambiguazione – Se stai cercando altri significati, vedi Combinazione (disambigua).

Si definisce combinazione di n elementi presi k alla volta (oppure di n elementi di classe k oppure di n elementi a k a k) ogni sottoinsieme di k elementi estratti da un insieme di n elementi.

E' utilizzata nel calcolo combinatorio, se n e k sono due interi positivi. Si parla di combinazione semplice se essa non può avere elementi che si ripetono e di combinazione con ripetizione altrimenti. Nel caso di combinazioni semplici deve risultare necessariamente kn.

In entrambi i casi i sottoinsiemi vanno considerati indipendentemente 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, i gruppi prs, psr, rps, spr, rsp ed srp rappresentano la stessa combinazione in quanto formati dagli stessi elementi mentre i gruppi prs ed srq rappresentano due diverse combinazioni in quanto differiscono in almeno uno degli elementi.

Combinazioni semplici

Dato un insieme A di cardinalità n, il numero dei sottoinsiemi di A di cardinalità kn, vale a dire le combinazioni di n elementi presi a k a k, si ottiene dividendo il numero di tutti i possibili sottoinsiemi 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:

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:

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:

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

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:

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

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:

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

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

Multinsiemi

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:

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

Template:Wikilibro

Altri progetti

Collegamenti esterni

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