Calcolo combinatorio: teoria, formule ed esercizi svolti

Autori: Francesco Tamberi.

Revisori: Sergio Fiorucci.

Il calcolo combinatorio è la branca della matematica che si occupa dello studio dei modi in cui si possono associare, o ordinare, gli elementi di uno o più insiemi finiti; nella fattispecie il calcolo combinatorio è utile per determinare il numero dei possibili modi in cui questi elementi si possono raggruppare.

Vediamo un esempio su come si contano i raggruppamenti:

Svolgimento. Un primo approccio è quello di costruire l’albero delle scelte e contare le relative foglie:

Dall’albero si capisce subito che è possibile comporre un totale di sei pizze:

1. impasto bianco e funghi

 

2. impasto bianco e salame

 

3. impasto bianco e verdure

 

4. impasto integrale e funghi

 

5. impasto integrale e salame

 

6. impasto integrale e verdure

Un altro possibile approccio consiste nel considerare i due insiemi:

Le possibili pizze sono gli elementi del prodotto cartesiano , ovvero tutte le coppie che posso formare prendendo un elemento dall’insieme I ed un elemento dall’insieme T:

dato che ho due modi di scegliere un elemento da I e tre modi di scegliere un elemento da T il numero totale di pizze è:

Purtroppo, al contrario di quanto appena visto, spesso non è possibile contare manualmente il numero di elementi che ci viene richiesto, per questo nei prossimi capitoli presenteremo i vari tipi di raggruppamento e le relative metodologie di calcolo.

Il problema generico, insiemisticamente parlando, è quello di contare le sequenze di elementi che si possono formare da un insieme di elementi distinti; se le sequenze differiscono tra loro per qualche elemento o per l’ordine in cui essi sono disposti, si parla di disposizioni.

Nei prossimi due paragrafi distingueremo tra disposizioni semplici (per le quali un singolo elemento non può ripetersi) e disposizioni con ripetizione (per le quali invece la ripetizione è concessa).

Come specificato sono disposizioni semplici le sequenze ordinate di elementi (classe k), estratte da un insieme di elementi distinti, che non presentano ripetizioni; è immediato dedurre che si ha .

Esempi di disposizioni semplici possono essere:

le possibili combinazioni del podio in una maratona;

i modi in cui disporre una parte dei vostri libri su una mensola;

i numeri compresi tra 100 e 999 che posso formare usando soltanto cifre dispari e senza ripetizioni.

Per capire come arrivare alla formula facciamo un esempio pratico in cui vogliamo contare i possibili sottoinsiemi ordinati contenenti 3 palline da un insieme di 9 palline numerate; immaginiamo uno di questi sottoinsiemi come formato da tanti slot quanti sono gli elementi che vogliamo:

Riempiamo uno slot alla volta: in quanti modi posso riempire il primo? Ho tutte e 9 le palline a mia disposizione, quindi posso riempirlo in 9 modi diversi.

Supponiamo di inserire la pallina numero 4 nel primo slot:

Riempito il primo slot passiamo al secondo: per la seconda posizione ci rimangono 8 palline, quindi abbiamo 8 possibilità.

Scegliamo di inserire la pallina numero 2 nel secondo slot:

Come esposto ho 9 possibili scelte per la prima posizione, per ognuna di queste ho 8 possibili scelte per la seconda e per ognuna delle scelte fatte ho 7 possibili scelte per la terza, per un totale di possibili terne diverse.

Quanto appena fatto è analogo a quanto visto con l’albero del primo capitolo, chiaramente difficile da implementare con così tante aperture; generalizzando il ragionamento otteniamo il seguente risultato: