Definizione delle tipologie di permutazioni ed esempi numerici

(320 punti)

7' di lettura

In questo appunto di Matematica viene trattato il concetto di permutazione, ovvero tutti i possibili modi di raggruppare una sequenza di oggetti. Una volta fornita la definizione matematica, verranno descritte le diverse tipologie di permutazione e verranno forniti diversi esempi.

Definizione

La permutazione è una tipologia di raggruppamento di elementi di vario tipo all’interno di una sequenza. Dato

[math] n [/math]

il numero degli oggetti e

[math] k [/math]

il numero dei posti di una sequenza, considerando l’ordine con cui si dispongono gli oggetti, tutti i possibili raggruppamenti tali che

[math] n = k [/math]

sono detti permutazioni di tali elementi.

Permutazioni senza ripetizioni (Semplice)

Quando gli

[math] n [/math]

oggetti da permutare sono tutti tra loro distinguibili, senza ripetizioni, allora la permutazione viene detta semplice.
Per il calcolo del numero di permutazioni semplici si procede come segue:

Si sceglie il primo oggetto fra gli
[math] n [/math]
disponibili; questo, naturalmente, può essere fatto esattamente in n modi diversi.
Si sceglie, poi, il secondo oggetto; considerando che il primo oggetto è stato già scelto e che non vi possono essere ripetizioni, rimangono, dunque,
[math] n-1 [/math]
oggetti tra cui selezionare il secondo.
Procedendo così, il numero di oggetti diminuisce ad ogni successione; al terzo passo rimarranno
[math] n-2
[/math]
oggetti, al quarto
[math] n-3 [/math]
e così via.
All’ultima successione rimarrà un solo oggetto da scegliere, pertanto l’ultima scelta sarà obbligata dal momento che saranno terminati gli oggetti.

Per quantificare il numero di permutazioni dobbiamo considerare che per ognuna delle scelte effettuate, tutte le successive sono ancora disponibili. Ciò significa che il numero totale di permutazioni sarà dato da:

[math] n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 \cdot [/math]

ovvero il fattoriale

[math] P_n = n! [/math]

Permutazioni con Ripetizioni

Supponiamo adesso di avere

[math]n[/math]

oggetti con ripetizioni, che siano organizzabili in

[math]m[/math]

sottoinsiemi composti ciascuno da oggetti tutti uguali.
Sia

[math] r_j [/math]

il numero di oggetti appartenenti al j-esimo sottoinsieme; ne consegue che

[math]( r_1 + r_2 + \ldots + r_m = n )[/math]

Per determinare il numero di permutazioni con ripetizioni si procede come segue:

Determiniamo innanzitutto il numero di permutazioni senza ripetizioni relativo agli oggetti dati, come nel caso della permutazione semplice e dunque considerandoli come se fossero tutti diversi; dal caso della permutazione semplice segue che tale numero sia pari al fattoriale
[math]n![/math]
.
Si fissa adesso una di tali permutazioni considerando tutti gli oggetti appartenenti al primo sottoinsieme che figurano in essa, ovvero
[math]r_1[/math]
: se permutiamo tra loro, in un modo qualsiasi, solo gli oggetti del primo sottoinsieme e lasciamo fissi tutti gli altri, otteniamo ancora la stessa permutazione generale, poiché gli oggetti sono tra loro tutti uguali. Queste permutazioni, dalla formula della permutazione semplice, sono in totale
[math] r_1! [/math]
e vanno considerate uguali al fine del calcolo che stiamo effettuando. Dunque il numero
[math]n![/math]
va diviso per
[math]r_1![/math]
.
Estendiamo il ragionamento fatto per il primo sottoinsieme a tutti gli altri sottoinsiemi di oggetti rimanenti, per cui il numero di permutazioni con ripetizioni sarà pari a

[math] P_n^r = \frac{n!}{r_1! r_2!\ldots r_m!} [/math]

Osservazioni

Osservazione 1: Consideriamo la formula per il calcolo del numero di permutazioni con ripetizioni relativo ad

[math]n[/math]

oggetti tutti differenti. In questo caso possiamo comunque adoperare la formula per le permutazioni con ripetizioni, ma ciascuno dei sottoinsiemi sarà composto da un solo oggetto. Poiché il numero totale di oggetti dovrà essere sempre

[math]n[/math]

, va da sé che dovranno esserci tanti sottoinsiemi quanti sono gli oggetti, ovvero che

[math]n = m[/math]

. La formula

[math] P_n^r = \frac{n!}{r_1! r_2!\ldots r_m!} [/math]

allora risulta scritta come:

[math] P_n^r = \frac{n!}{r_1! r_2! \ldots r_n!} = \frac{n!}{1! 1! \ldots 1!} = n! = P_n [/math]

Risultando dunque in assoluto accordo con il fatto che gli oggetti erano tutti tra loro diversi; pertanto, avremmo potuto utilizzare anche la formula per la permutazione semplice. Dunque, nel caso che gli oggetti siano tutti diversi, i valori risultanti delle due formule coincidono.
Osservazione 2: Se si hanno, però, anche solo due oggetti uguali tra loro, il valore della formula della permutazione con ripetizioni è strettamente minore di quello del caso semplice.

Osservazione 3: In virtù delle proprietà del coefficiente binomiale, la formula nel caso con ripetizioni restituisce sempre un numero naturale per ogni possibile scelta degli oggetti. Ovviamente, ciò adesso assume significato visto che non avrebbe senso parlare di una quantità non intera o negativa di possibili raggruppamenti, dunque di permutazioni.

Esempi

Esempio 1: Tre squadre di atleti si sfidano in un torneo sportivo. Determina in quanti modi diversi esse potranno occupare il podio.
In questo esempio abbiamo 3 posti e 3 oggetti: i primi sono costituiti dai gradini del podio, mentre i secondi sono le tre squadre. Poiché naturalmente una stessa squadra non può occupare al contempo due diverse posizioni in classifica, si tratta di una permutazione senza ripetizioni.
Dunque,

[math] P_3 = 3! = 6 [/math]

Esempio 2: Ad una tavolata di 6 amici arrivano 3 pizze margherite, 2 alla marinara e 1 quattro formaggi. Calcola in quanti modi diversi tali pizze possono essere distribuite.
In tal caso immaginiamo di ordinare i 6 amici dal primo al sesto, considerandoli come posti, e di dividere i 6 oggetti, le pizze, in 3 famiglie composte da oggetti tutti uguali:

[math]r1=1[/math]

per la quattro formaggi,

[math]r2=2[/math]

per le marinare e

[math]r3=3[/math]

per le margherite.
Adoperando la formula nel caso di ripetizioni avremo subito

[math] P_6^r = \frac{6!}{1! 2! 3!} = \frac{3 \cdot 4 \cdot 5 \cdot 6}{1 \cdot 2 \cdot 3} = \frac{4 \cdot 5 \cdot 6}{2} = 3 \cdot 4 \cdot 5 = 60 [/math]

Pertanto, le pizze possono essere distribuite in ben 60 modi essenzialmente diversi. Adoperando la formula

[math] P_n^r = \frac{n!}{r_1! r_2!\ldots r_m!} [/math]