Combinazioni

Una combinazione è un raggruppamento di k elementi, presi in qualsiasi ordine, formato a partire da n elementi distinti. In termini più rigorosi si dice combinazione ogni sequenza di k elementi estratti tra n elementi distinti, nell'ipotesi che l'ordine di estrazione sia ininfluente.

 

Riassunto delle puntate precedenti: abbiamo introdotto le nozioni generali di permutazione e di disposizione, e abbiamo definito e analizzato i vari tipi di permutazioni e di disposizioni. Per farlo siamo partiti da n elementi e per comporre i raggruppamenti abbiamo sempre tenuto conto dell'ordine con cui gli elementi si susseguivano.

 

Non sempre però l'ordine degli elementi va preso in considerazione. Si pensi ad esempio al gioco del SuperEnalotto, in cui vengono estratti sei numeri e si vince se se ne indovinano due o più, indipendentemente dall'ordine con cui sono stati giocati e da quello con cui sono stati estratti. In questo e in tutti i casi in cui l'ordine degli elementi non ha importanza si parla di combinazioni.

 

Definizione di combinazione

 

Si definiscono combinazioni di classe k di n elementi distinti tutti i raggruppamenti che si possono formare a partire dagli n elementi, in modo che:

 

- ogni raggruppamento contenga esattamente k elementi;

 

- i vari raggruppamenti differiscano tra loro per almeno un elemento, ma non per l'ordine.

 

Se i k elementi di ogni raggruppamento devono essere distinti tra loro, si parla di combinazioni semplici. Se invece uno stesso elemento può essere ripetuto, si ha a che fare con combinazioni con ripetizione.

 

Nella definizione di combinazione non si fa alcun cenno sull'ordine dei raggruppamenti, vale a dire che i vari raggruppamenti vanno considerati indipendentemente dall'ordine con cui gli elementi si presentano.

 

Per chiarire ogni dubbio vediamo un esempio e determiniamo le combinazioni di classe 2 degli elementi dell'insieme A=\{a,b,c\}.

 

Ogni combinazione di classe 2 è un raggruppamento formato con 2 elementi di A. Inoltre ogni combinazione si distingue da un'altra se cambia almeno un elemento.

 

• Se i due elementi devono essere diversi tra loro, ossia se non sono ammesse ripetizioni, tutte le possibili combinazioni di classe 2 sono

 

ab \ \ ; \ \ ac \ \ ; \ \ bc

 

• Se invece sono ammesse ripetizioni, si hanno le seguenti combinazioni:

 

\\ aa \ \ ; \ \ bb \ \ ; \ \ cc \\ \\ ab \ \ ; \ \ ac \ \ ; \ \ bc

 

Proprio perché i raggruppamenti vanno presi indipendentemente dall'ordine degli elementi da cui sono composti, la sequenza ab e la sequenza ba rappresentano la stessa combinazione, dunque si deve considerare solo una delle due e la scelta è del tutto ininfluente.

 

Lo stesso ragionamento vale per i raggruppamenti ac e ca e per i gruppi bc e cb.

 

Tipi di combinazioni

 

Esistono due tipi di combinazioni: le combinazioni semplici (o combinazioni senza ripetizione) e le combinazioni con ripetizione.

 

Come suggeriscono i nomi stessi, la differenza tra i due tipi di combinazioni è che le combinazioni semplici sono formate da k elementi distinti tra loro, mentre nelle combinazioni con ripetizione uno stesso elemento può essere ripetuto fino a k volte.

 

Passiamo alle definizioni e alle formule con cui si calcolano il numero di combinazioni semplici e il numero di combinazioni con ripetizione.

 

Combinazioni semplici (dette anche combinazioni senza ripetizione)

 

Si dice combinazione semplice ogni sequenza di k elementi distinti estratti tra n elementi distinti, indipendentemente dall'ordine e con n \ge k.

 

Il numero di combinazioni semplici si indica con C_{n,k} ed è dato dal coefficiente binomiale n su k

 

C_{n,k} = \dbinom{n}{k} = \frac{n!}{k!(n-k)!}

 

 

Combinazioni con ripetizione

 

Si dice combinazione con ripetizione ogni sequenza di k elementi estratti tra n elementi distinti, con la possibilità che ogni elemento possa ripetersi fino a k volte all'interno della stessa sequenza, e indipendentemente dall'ordine.

 

Il numero di combinazioni con ripetizione si indica con C'_{n,k} ed è uguale al coefficiente binomiale n+k-1 su k

 

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

 

Esempi sulle combinazioni

 

1) Elencare e calcolare il numero di combinazioni semplici di classe 3 degli elementi dell'insieme definito per caratteristica:

 

E_1=\{x \ | \ x \ \grave{\mbox{e}} \mbox{ una vocale della parola "aiuola"}\}

 

Svolgimento: scriviamo esplicitamente gli elementi di E_1, ossia rappresentiamo l'insieme per elencazione

 

E_1=\{a,i,u,o\}

 

La vocale a va riportata una sola volta, anche se compare due volte nella parola aiuola. Questo perché, per definizione di insieme, i suoi elementi devono essere distinti tra loro.

 

Abbiamo dunque un insieme formato da 4 elementi di cui vogliamo trovare le combinazioni semplici di classe 3. Ognuna di tali combinazioni è una sequenza di tre elementi distinti di E_1, e ogni sequenza è diversa dall'altra solo se è diverso almeno un elemento.

 

Scegliamo allora tre qualsiasi elementi di E_1 e scriviamoli l'uno di seguito all'altro, ottenendo così una delle combinazioni di classe 3:

 

aiu

 

Per ricavare le altre partiamo da questa sequenza e sostituiamo ciascuna vocale con quella esclusa - nel nostro caso o - mantenendo fisse le altre due.

 

- Sostituendo la a abbiamo la combinazione oiu

 

- Sostituendo la i otteniamo la combinazione aou

 

- Sostituendo la u ricaviamo la combinazione aio

 

In sintesi, le combinazioni semplici di classe 3 degli elementi di E_2 sono:

 

aiu \ \ ; \ \ oiu \ \ ; \ \ aou \ \ ; \ \ aio

 

Badate bene che nulla ci vieta di scambiare l'ordine degli elementi delle singole combinazioni. Più esplicitamente, ogni permutazione degli elementi delle singole combinazioni individua la stessa combinazione.

 

Per concludere l'esercizio verifichiamo che le combinazioni di classe 3 degli elementi di E_1 sono proprio quattro. Dalla formula delle combinazioni semplici sappiamo che

 

C_{n,k}=\dbinom{n}{k} = \frac{n!}{k!(n-k)!}

 

dove n e k rappresentano, rispettivamente, il numero degli elementi dell'insieme e la classe della combinazione. Sostituiamo n=4 e k=3

 

C_{4,3}=\dbinom{4}{3} = \frac{4!}{3!(4-3)!} =\frac{4!}{3! \cdot 1!}=

 

calcoliamo i fattoriali e semplifichiamo

 

=\frac{24}{6}=4

 

 

2) Quali e quante sono le combinazioni con ripetizione di classe 3 degli elementi dell'insieme E_2=\{s,t\}?

 

Svolgimento: le combinazioni con ripetizione di classe 3 degli elementi di E_2=\{s,t\} sono tutti i gruppi di tre elementi composti con s,t, che differiscono tra loro per almeno un elemento e in cui ciascun elemento può essere ripetuto fino a un massimo di tre volte.

 

Le alternative possibili sono:

 

- un gruppo formato da tre s,

 

- un gruppo formato da due s e da una t,

 

- un gruppo formato da una s e da due t,

 

- un gruppo formato da tre t,

 

ossia

 

sss \ \ ; \ \ sst \ \ ; \ \ stt \ \ ; \ \ ttt

 

Anche in questo caso l'ordine degli elementi di ogni combinazione non ha alcuna importanza. Ad esempio la combinazione formata da due s e da una t si può rappresentare, indistintamente, in uno dei seguenti modi

 

sst \ \ ; \ \ sts \ \ ; \ \ tss

 

In conclusione le combinazioni con ripetizione di classe 3 degli elementi di E_2 sono quattro. Ciò viene confermato anche dalla formula sulle combinazioni con ripetizione

 

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

 

in cui sostituiamo n=2 e k=3

 

C'_{2,3} = \frac{(2+3-1)!}{3! \cdot (2-1)!} = \frac{4!}{3! \cdot 1!} = \frac{24}{6} = 4

 

 


 

Dopo questa infarinatura generale sul concetto di combinazione vi invitiamo a non perdervi le prossime lezioni. Ci occuperemo prima delle combinazioni semplici e poi delle combinazioni con ripetizione: riproporremo le definizioni spiegandole in maniera più accurata, dimostreremo le formule per il calcolo del numero di combinazioni semplici e con ripetizione, e vedremo altri esempi.

 

Per tutto il resto vi ricordiamo che qui su YM ci sono migliaia di esercizi risolti e altrettante lezioni, a partire dalla scheda di esercizi svolti sulle combinazioni, e che potete trovare tutto quello che vi serve con la barra di ricerca interna. ;)

 

 

Buon proseguimento su YouMath,

Giuseppe Carichino (Galois)

 

Lezione precedente.....Esercizi correlati.....Lezione successiva

 
 

Tags: cos'è una combinazione - tipi di combinazioni - numero di combinazioni di classe k - differenza tra combinazioni semplici e combinazioni con ripetizione.