Permutazioni
 

Calcolo combinatorio



Il calcolo combinatorio è la branca della matematica che studia i modi per raggruppare, seguendo determinate regole, gli elementi appartenenti a insiemi finiti di oggetti.


Regola del prodotto o teorema fondamentale del calcolo combinatorio



Questa regola ci consente di calcolare in quanti modi è possibile combinare tra loro gli oggetti a nostra disposizione. Per comprendere meglio il meccanismo che è alla base di questa regola, possiamo rappresentare le combinazioni possibili tra tali oggetti con un albero capovolto all'interno del quale ogni diramazione rappresenta la scelta possibile tra due di tali oggetti. Contando tutte le diramazioni all'estremità inferiore di tale albero, sapremo il massimo numero di combinazioni possibili tra gli oggetti. Chiariamo con un esempio.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


L'esempio che abbiamo visto considera un numero non troppo alto di oggetti a nostra disposizione. Tuttavia, quando il numero cresce, l'albero può diventare troppo grande e difficile da rappresentare. Cerchiamo allora di trovare una regola matematica che ci consenta di calcolare il massimo numero di combinazioni possibili.


Nell'esempio abbiamo compiuto delle scelte in 3 fasi per ottenere combinazioni formate da 3 oggetti (giacca + borsa + scarpe):

  • nella prima fase abbiamo scelto la giacca e avevamo a disposizione un numero di oggetti possibili (nera o blu),

  • nella seconda fase abbiamo scelto la borsa e avevamo a disposizione un numero di oggetti possibili (nera, bianca o rossa)

  • nella terza fase abbiamo scelto le scarpe e avevamo a disposizione un numero di oggetti possibili (nere o rosse).


Contando i rami terminali dell'albero, abbiamo visto che il numero massimo di combinazioni possibili è uguale a 12 che è esattamente uguale al prodotto del numero di elementi a disposizione in ogni fase di scelta:




Supponiamo ora di avere a disposizione un numero k di fasi per selezionare oggetti all'interno di insiemi ogni volta contenenti un diverso numero di elementi:

  • nella prima fase abbiamo elementi a disposizione,

  • nella seconda fase abbiamo elementi a disposizione,

  • ...,

  • nella k-esima fase abbiamo elementi a disposizione.


Naturalmente dobbiamo tenere presente che la nostra selezione ad ogni fase è indipendente da ciò che abbiamo selezionato nella fase precedente.


Se inizialmente effettuiamo una scelta tra elementi, quindi, indipendentemente da tale scelta, effettuiamo una scelta tra elementi, ... e infine, indipendentemente dalla scelta precedente, effettuiamo una selezione tra elementi, il numero totale di combinazioni (N) è pari al prodotto del numero di elementi () che abbiamo a disposizione ad ogni fase:




Vediamo un altro esempio.


Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Regola della somma



Consideriamo ora il caso in cui abbiamo insiemi separati (quindi senza elementi in comune) e la possibilità di scegliere un solo elemento di uno solo degli insiemi.


In questo caso potremo selezionare tra:


  • elementi del primo insieme

    oppure

  • elementi del secondo insieme

    oppure

  • ...

    oppure

  • elementi del k-esimo insieme


La scelta di un elemento di un insieme è quindi incompatibile con le scelta di altri elementi nei restanti insiemi. Se scegliamo un elemento da un insieme non possiamo allo stesso tempo sceglierne altri appartenenti agli altri insiemi.


Se possiamo selezionare un solo elemento tra gli elementi di un primo insieme oppure un solo elemento tra gli elementi del secondo insieme... oppure un solo elemento tra gli elementi dell'ultimo insieme, allora il massimo numero di possibilità di scelta (M) che abbiamo, è dato dalla somma del numero di elementi () appartenenti a ciascun insieme:




Esempio

Gli esempi sono visibili solo per gli utenti registrati
 
 
Registrati per vedere gli esempi »


Tipologie di sequenze nel calcolo combinatorio



Per poter distinguere i diversi tipi di sequenze di oggetti che possiamo combinare tra loro, dobbiamo porci le seguenti domande:


  • l'ordine in cui compaiono gli oggetti in una sequenza è importante ? Ovvero, se abbiamo tre elementi A, B e C, la sequenza ABC è considerata uguale a CBA oppure si tratta di due sequenze distinte ?

  • gli oggetti possono essere ripetuti all'interno di una sequenza ? Ovvero, se abbiamo gli elementi A e B, possiamo avere solo sequenze del tipo AB e BA oppure posso avere sequenze del tipo AA, BB, AB, etc. ?


Quando l'ordine col quale vengono selezionati e disposti gli oggetti è importante, si parla di:



Quando l'ordine col quale vengono selezionati e disposti gli oggetti non è importante, si parla di:


redattore del materiale didattico: Carmine Albanese