Calcolo combinatorio

Permutazioni semplici

Supponiamo di avere quattro tazze colorate ognuna di un colore diverso (giallo, bianco, verde, blu) e di voler metterle tutte in fila.

Ora, chiediamoci:

In quanti modi le quattro tazze possono essere messe in fila in modo che ogni sequenza differisca dalle altre per l'ordine con cui le tazze sono disposte?

Nel calcolo combinatorio, il numero degli ordinamenti di n oggetti distinti presi da un dato insieme di n oggetti prende il nome di permutazioni semplici di n oggetti e si indica con il simbolo P_n. Il termine "semplici" sta ad indicare che non si possono ripetere gli stessi oggetti all'interno di ogni permutazione. Nel nostro caso le operazioni da eseguire sono solo quelle di scambiare di posto le quattro tazze, variando l'ordine, per trovare tutti i possibili ordinamenti, come si fa quando avendo a disposizione quattro lettere (R, A, M, O) si vuole formare tutti i possibili anagrammi di quattro lettere considerando anche quelli privi di significato. Ad esempio, se consideriamo la sequenza iniziale delle quattro tazze e scambiamo di posto la tazza gialla con la tazza verde si ha una sequenza ordinata diversa perchè l'ordine delle quattro tazze è diverso come si vede in figura.

Con un grafo ad albero possiamo visualizzare tutte le possibili permutazioni delle quattro tazze (per semplicità indicheremo le tazze solo con le lettere A, B, C, D) e farne un elenco completo. Si inizia con quattro rami per occupare il primo posto nella fila con una qualsiasi delle quattro tazze A, B, C, D. Ognuno dei quattro rami genera a sua volta tre rami, uno per ciascuna delle tre tazze rimaste. Sistemate le prime due tazze, andiamo a sistemare la terza tazza: sarà una delle due rimaste, riportate su uno dei due rami che seguono. Si arriva cosí all'ultima ramificazione con un solo ramo: è la quarta tazza, che andrà ad occupare l'ultimo posto in fila.

Una volta tracciato il grafo è molto semplice scrivere e contare tutte le permutazioni, basterà annotare di seguito le lettere in ogni ramo dell'albero.

Con pochi oggetti è facile tracciare l'albero e contare tutte le permutazioni che nel nostro caso sono 24. La rappresentazione grafica con il relativo conteggio diventa molto complicata quando gli oggetti da ordinare sono tanti. Ci si pone allora la domanda:

E' possibile, conoscendo il numero degli oggetti da ordinare, sapere subito il numero delle permutazioni senza dover contarle?

Osservando il grafo ad albero si vede che il primo posto della fila può essere scelto in 4 modi, il secondo in 3 modi, il terzo in 2 modi e il quarto in 1 modo solo (è una scelta obbligata). I percorsi possibili sono dunque 4⋅3⋅2⋅1=24 e questo è il numero delle file che si possono ottenere. Da questa osservazione si intuisce che se la tazze fossero 5 il numero delle posibili permutazioni risulterebbero

5⋅4⋅3⋅2⋅1=120

E se le tazze fossero n le possibili permutazioni risulterebbero

n⋅(n-1)⋅(n-2)⋅(n-3)⋅ ... ⋅3⋅2⋅1

In matematica, il prodotto di n fattori interi decrescenti da n ad 1 si chiama fattoriale di n e si indica con il simbolo n! (si legge n fattoriale), per convenzione si pone 0!=1 e 1!=1. Possiamo quindi dire che il numero complessivo di permutazioni semplici di n oggetti distinti è dato dalla formula:

P_n = n! = n⋅(n-1)⋅(n-2)⋅(n-3)⋅ ... ⋅3⋅2⋅1

Come si può facilmente intuire il numero delle permutazioni cresce rapidamente con il crescere del numero degli oggetti. Vediamo alcuni valori di n e P_n

n	1	2	3	4	5	6	7	8	9	10
Pn	1	2	6	24	120	720	5.040	40.320	362.880	3.628.800