Calcolo combinatorio

Permutazioni con ripetizioni

Supponiamo di avere tre tazze di colore giallo (uguali tra loro) e due tazze di colore verde (uguali tra loro) e di voler metterle in fila.

Ora, chiediamoci:

quante file ordinate delle nostre cinque tazze non tutte distinte tra loro sono possibili in modo che ogni sequenza differisca dalle altre per l'ordine con cui le tazze sono disposte?

Attenzione! In questo caso le tre tazze di colore giallo o le due tazze di colore verde non sono distinguibili tra loro e quindi non siamo nella situazione precedente delle permutazioni semplici. Nel calcolo combinatorio, gli ordinamenti distinti di n oggetti non tutti distinti tra loro presi da un dato insieme di n oggetti prendono il nome di permutazioni con ripetizione di n oggetti. Come possiamo calcolare il numero delle permutazioni con ripetizione? Supponiamo che le tre tazze gialle e le due tazze verdi siano distinguibili tra loro. Ad esempio, possiamo supporre che le tre tazze gialle e le due tazze verdi abbiano un'etichetta in modo da poterle distinguere.

In tal caso le permutazioni semplici sono:

P₅ = 5! = 5⋅4⋅3⋅2⋅1 = 120

Se per esempio, consideriamo tutte le sequenze in cui le tre tazze gialle etichettate occupano la prima, la terza e la quarta posizione e le due tazze verdi etichettate occupano la seconda e la quarta posizione notiamo che le permutazioni semplici possibili sono 12. E ciò si verifica perchè i modi di permutare le tre tazze gialle sono 3! = 6 e il numero di modi di permutare le due tazze verdi sono 2! = 2 e quindi i modi di permutare sono 3!⋅2!=12.

Ora, se togliamo da queste 12 permutazioni semplici le etichette a tutte le tazze otteniamo sempre la stessa permutazione con ripetizione perchè le tre tazze gialle non sono distinguibili tra loro e pure le due tazze verdi non sono distinguibili tra loro.

Si intuisce allora che nel nostro esempio di 5 tazze in cui 3 sono gialle e due sono verdi ad ogni gruppo di 12 permutazioni semplici corrisponde una sola permutazione con ripetizione e quindi le permutazioni con ripetizione sono in tutto 120 : 12 = 10. Infatti, se indichiamo con x il numero delle permutazioni con ripetizioni di 5 tazze (3 gialle e 2 verdi) possiamo scrivere la seguente uguaglianza:

In generale il numero di permutazioni di n oggetti di cui k₁ uguali tra loro, k₂ uguali tra loro e distinti dai precedenti, ... , k_n uguali tra loro e distinti dai precedenti e con k₁+k₂+...+k_n=n è dato dalla formula: