Ci siamo occupati delle permutazioni semplici, cioè degli scambi tra elementi distinti tra loro. Ma cosa succede se gli elementi non sono distinti? Risponderemo a questa domanda in questa lezione affrontando le permutazioni con ripetizione, ossia delle permutazioni in cui ci sono degli elementi che si ripetono.
DEFINIZIONE DI PERMUTAZIONE CON RIPETIZIONE
Per capire meglio cosa stiamo affrontando vediamo subito un esempio. Prendiamo il numero “$1224$” e calcoliamo le permutazioni delle sue cifre. Per il momento ignoriamo che la cifra $2$ sia ripetuta due volte e consideriamole come diverse (utilizzando colori diversi).
Se calcoliamo le permutazioni semplici di $4$ elementi otteniamo $P_4=4!=24$.
Quindi dovrebbero esserci $24$ permutazioni possibili delle cifre del numero “$1224$”. Se le rappresentiamo graficamente, otteniamo la seguente lista di permutazioni:
Alle permutazioni però non interessa il colore degli elementi ma solo il loro ordine. Ci sono quindi delle permutazioni uguali (con gli elementi nello stesso ordine), in figura sono cerchiate due di queste ma ce ne sono molte altre! In pratica la formula delle permutazioni semplici non funziona perché ci fa contare la stessa permutazione più volte. Tutto questo è dovuto al fatto che l’elemento $2$ è ripetuto più di una volta. Dobbiamo quindi trovare un modo di contare le permutazioni senza i “doppioni” dovuti all’elemento ripetuto.
Osserviamo che nel nostro esempio le permutazioni si ripetono a coppie, differiscono solo per i colori dei $2$ scambiati. Beh se andiamo a trovare tutte le altre coppie uguali in figura arriveremo al risultato di $12$ coppie di permutazioni uguali. Quindi le permutazioni del numero “$1224$” non sono $24$ ma $12$, tutte le altre sono dei doppioni.
Indichiamo il risultato come $P_4^{(2)}=12$, cioè le permutazioni di $4$ elementi di cui $2$ ripetuti.
Se dovessimo usare questo procedimento per ogni esercizio rischieremo di perdere anni della nostra vita sulle permutazioni. Ci sono infatti esercizi ben più complicati, in cui lo stesso elemento viene molte più volte (ad esempio le permutazioni del numero “$122224$”) o casi in cui più di un elemento viene ripetuto (ad esempio le permutazioni del numero $111122224444$).
Cerchiamo quindi una formula che velocizzi i nostri calcoli ma prima vediamo la definizione più formale di permutazione con ripetizione:
Dati $n$ elementi, di cui alcuni ripetuti $n_1,n_2,n_3,…$ volte con $n_1+n_2+n_3+…\le n$, le permutazioni con ripetizione sono tutti i gruppi di $n$ elementi che differiscono tra loro per l’ordine degli elementi distinti. Dati $n$ ed $n_1,n_2,n_3,…$ il numero di permutazioni con ripetizione è dato dalla formula: $P_n^{(n_1,n_2,n_3,…)}=\dfrac{n!}{n_1!\cdot n_2!\cdot n_3!\cdot …}$
Elenchiamo alcune caratteristiche delle permutazioni con ripetizione:
- gli $n$ elementi possono ripetersi più di una volta
- $n_1, n_2, n_3,…\in \mathbb{N}$ sono i numeri che indicano quante volte si ripetono i vari elementi
- il numero di volte con cui alcuni elementi si ripetono deve essere sicuramente minore nel numero totale di elementi, vale quindi $n_1+n_2+n_3+…\le n$
- il simbolo $n!$ è il fattoriale del numero $n$, così come $n_1!,n_2!,…$ sono i fattoriali dei numeri $n_1,n_2,…$
- l’ordine degli elementi distinti è importante
- $n\in \mathbb{N}$
Non resta altro che andare a vedere qualche esempio!
esempio
Calcola quante sono gli anagrammi (anche privi di significato) della parola “CEPPO”.
Per anagramma si intende lo scambio di ordine delle lettere di una parola. La parola “CEPPO” è formata da $5$ elementi: $C,E,P,P,O$. Gli anagrammi saranno sempre parole di $5$ lettere in cui l’ordine è importante e siccome la lettera $P$ compare $2$ volte possiamo contare gli anagrammi come fossero delle permutazioni di $n=5$ elementi di cui un elemento è ripetuto $n_1=2$ volte.
Quindi andiamo ad utilizzare la formula appena vista:
$P_n^{(n_1,n_2,n_3,…)}=\dfrac{n!}{n_1!\cdot n_2!\cdot n_3!\cdot …}$
nel nostro caso abbiamo $n=5$ e $n_1=2$, questo significa che $n_2,n_3,…=1$. Sostituendo i valori la formula diventa:
$P_5^{2}=\dfrac{5!}{2!}=\dfrac{120}{2}=60$
Abbiamo quindi $60$ anagrammi diversi della parola “CEPPO”.
Vediamo un altro esempio.
Quanti numeri diversi si possono scrivere utilizzando tutte le cifre del numero “$251522$”?
Siccome il numero “$31132$” ha sei cifre, i numeri che si possono formare avranno anch’essi sei cifre perché dobbiamo usare tutti gli elementi a disponibili. Alcuni elementi da usare sono ripetuti, infatti sia la cifra $5$ che la cifra $2$ sono ripetute rispettivamente due e tre volte.
Essendo che l’ordine è importante, i numeri che si possono scrive possono essere visti come delle permutazioni con ripetizione di $n=6$ elementi. Pensiamo ora agli elementi ripetuti, la cifra $2$ viene ripetuta tre volte quindi $n_1=3$, mentre la cifra $5$ viene ripetuta due volte quindi $n_2=2$.
Utilizzando la formula per le ripetizioni con ripetizione $P_n^{(n_1,n_2)}=\dfrac{n!}{n_1!\cdot n_2!}$ e inserendo i valori trovati otteniamo:
$P_6^{(3,2)}=\dfrac{6!}{3!\cdot 2!}=\dfrac{720}{6\cdot 2}=60$
Esercizi svolti su permutazioni con ripetizione? Ecco QUI