Permutazioni con ripetizione

Si definisce permutazione con ripetizione una permutazione di elementi non tutti distinti tra loro; in altre parole una permutazione con ripetizione è uno dei possibili modi per ordinare totalmente un certo numero di elementi, di cui alcuni ripetuti.

 

Nelle precedenti puntate del corso sul Calcolo Combinatorio abbiamo introdotto il concetto di permutazione e abbiamo imparato a calcolare il numero di permutazioni semplici, ossia il numero di permutazioni di n oggetti diversi tra loro. Ora vedremo come comportarci quando tra gli elementi da permutare ve ne sono alcuni che si ripetono due o più volte.

 

Questa lezione è incentrata sulle permutazioni con ripetizioni: ne riporteremo la definizione e impareremo a calcolare il numero di permutazioni con ripetizione, fornendo la dimostrazione della formula e proponendo qualche esempio di applicazione.

 

Definizione di permutazione con ripetizione

 

Supponiamo di avere n elementi non tutti distinti. Si dicono permutazioni con ripetizione tutti i raggruppamenti che si possono formare con gli elementi considerati, in modo che:

 

- ciascun raggruppamento sia costituito da tutti e soli gli n elementi;

 

- ogni raggruppamento differisca dagli altri per l'ordine con cui gli elementi sono disposti.

 

Mettiamo in pratica la definizione di permutazione con ripetizione applicandola in un esempio. Ci riproponiamo di scrivere tutte le permutazioni degli elementi a,a,b.

 

Ogni permutazione deve contenere tutti e tre gli elementi, e si deve distinguere dalle altre per l'ordine con cui vengono scritti.

 

Scegliamo la prima lettera, che può essere a oppure b.

 

• Se viene scelta la lettera b, le altre lettere saranno le due a rimaste, dunque abbiamo la permutazione baa.

 

• Se consideriamo come lettera iniziale la a, per la seconda posizione abbiamo due possibili scelte: optare per l'altra lettera a oppure per la b. In entrambi i casi la scelta della terza lettera è obbligata:

 

- nel primo sarà la b, da cui la permutazione aab;

 

- nel secondo sarà la a rimanente, quindi otteniamo la permutazione aba.

 

In sintesi le permutazioni con ripetizione degli elementi a,a,b sono:

 

baa \ \ ; \ \ aab \ \ ; \ \ aba

 

Calcolo del numero di permutazioni con ripetizione

 

Consideriamo n elementi, alcuni dei quali indistinguibili, e supponiamo che n_1 siano di un tipo, che n_2 siano di un altro tipo, e così via fino a n_k, con la condizione che sia n_1+n_2+...+n_k=n.

 

Il numero di permutazioni con ripetizione degli n elementi così assegnati si indica con P_n^{n_1,n_2,...,n_k}, ed è dato dal rapporto tra il fattoriale di n e il prodotto dei fattoriali di n_1, n_2, ..., n_k

 

P_n^{n_1,n_2,...,n_k} = \frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}\\ \\ \mbox{con }n_1+n_2+...+n_k=n

 

Il vantaggio della formula per il calcolo del numero di permutazioni con ripetizione è che possiamo determinare il numero di permutazioni senza doverle determinare esplicitamente.

 

Torniamo per un momento al precedente esempio, in cui abbiamo individuato le permutazioni con ripetizione degli elementi a,a,b, e verifichiamo che sono proprio 3.

 

Vi sono n=3 elementi, di cui:

 

n_1=2 uguali alla lettera a;

 

n_2=1 uguali alla lettera b.

 

Usando la formula ricaviamo che il numero di permutazioni con ripetizione degli elementi a,a,b è dato da

 

P_n^{n_1,n_2} = P_3^{2,1} = \frac{3!}{2! \cdot 1!} = \frac{6}{2 \cdot 1} = 3

 

Dimostrazione della formula per il numero di permutazioni con ripetizione

 

Passiamo alla dimostrazione della formula. Vogliamo provare che il numero di permutazioni con ripetizione di n elementi, di cui n_1 di tipo 1, n_2 di tipo 2, ..., ed n_k di tipo k, con n_1+n_2+...+n_k=n, è dato da

 

P_n^{n_1,n_2,...,n_k} = \frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}\\ \\ \mbox{con }n_1+n_2+...+n_k=n

 

Dimostrazione

 

Supponiamo di avere n caselle e di doverle riempire con altrettanti elementi, di cui sappiamo che n_1 sono di tipo 1, n_2 sono di tipo 2, ..., ed n_k sono di tipo k, con la condizione che sia n_1+n_2+...+n_k=n.

 

Il numero di modi con cui si possono riempire le n caselle con i suddetti elementi è uguale al numero di permutazioni con ripetizione.

 

Per calcolare quanti sono ragioniamo per passi successivi. Prima però ricordiamo che il coefficiente binomiale n su k, indicato con \dbinom{n}{k}, rappresenta il numero di modi in cui k elementi possono essere scelti tra n, a prescindere dall'ordine.

 

Passo 1) Scegliamo n_1 caselle in cui disporre gli elementi di tipo 1. Tale scelta può essere fatta in \dbinom{n}{n_1} modi.

 

Passo 2) Tra le n-n_1 caselle rimaste libere, scegliamo n_2 caselle in cui disporre gli elementi di tipo 2. Ciò può essere fatto in \dbinom{n-n_1}{n_2} modi.

 

Passo 3) Tra le n-n_1-n_2 caselle rimaste libere, scegliamo n_3 caselle in cui disporre gli elementi di tipo 3. Ciò si può fare in \dbinom{n-n_1-n_2}{n_3} modi.

 

Passo k) Reiterando il procedimento arriviamo all'ultimo passo. Tra le n-n_2-....-n_{k-1} caselle rimaste libere scegliamo n_k caselle in cui disporre gli elementi di tipo k. Ciò si può fare in \dbinom{n-n_1-n_2-...-n_{k-1}}{n_k} modi.

 

Il numero totale di possibilità, ossia il numero di permutazioni con ripetizione, è dato da

 

\\ P_n^{n_1,n_2,...,n_k} = \\ \\ = \dbinom{n}{n_1} \cdot \dbinom{n-n_1}{n_2} \cdot \dbinom{n-n_1-n_2}{n_3} \cdot ... \cdot \dbinom{n-n_1-n_2-...-n_{k-1}}{n_k}=

 

esplicitiamo i coefficienti binomiali

 

\\ = \frac{n!}{n_1! \cdot (n-n_1)!} \cdot \frac{(n-n_1)!}{n_2! \cdot (n-n_1-n_2)!} \cdot \\ \\ \\ \cdot \frac{(n-n_1-n_2)!}{n_3! \cdot (n-n_1-n_2-n_3)!} \cdot ... \cdot \frac{(n-n_1-n_2-...-n_{k-1})!}{n_k!\cdot(n-n_1-n_2-...-n_k)!}=(\bullet)

 

Il secondo fattore di ogni denominatore si semplifica con il numeratore della frazione successiva. Inoltre l'ultimo secondo fattore a denominatore è pari a 0!=1, infatti

 

n-n_1-n_2-...-n_k=n-\overbrace{(n_1+n_2+...n_k)}^{n}=0

 

In conclusione:

 

(\bullet)=\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}

 

Osservazione sulla formula per il numero di permutazioni con ripetizione

 

Ciò che conta davvero nel conteggio delle permutazioni con ripetizione sono gli elementi che si ripetono più di una volta.

 

Per rendercene conto scriviamo la formula generale

 

P_n^{n_1,n_2,...,n_k}=\frac{n!}{n_1! \cdot n_2! \cdot ... \cdot n_k!}

 

e osserviamo che qualsiasi elemento presente n_i=1 volta dà un contributo pari a 1!=1, che non ha alcuna influenza sul prodotto a denominatore.

 

In sintesi tutte le volte che applichiamo la formula per il numero di permutazioni con ripetizione ci basta tenere conto degli elementi che si ripetono più di una volta.

 

Esempi sul calcolo del numero di permutazioni con ripetizione

 

1) Quanti anagrammi si possono formare con la parola cassa? E quanti con la parola matematica?

 

Svolgimento: in lingua italiana un anagramma è il risultato della permutazione delle lettere di una parola, tale da creare un'altra parola di senso compiuto. Nel Calcolo Combinatorio invece si conteggiano anche le parole prive di significato.

 

Ciò premesso gli anagrammi della parola cassa sono tanti quante sono le permutazioni delle lettere c, a, s, s, a, che evidentemente non sono tutte distinte tra loro. Vi sono infatti:

 

n_1=1 lettera c,

 

n_2=2 lettere a,

 

n_3=2 lettere s,

 

per un totale di n=5 elementi da permutare.

 

Per calcolare il numero di anagrammi di cassa usiamo dunque la formula delle permutazioni con ripetizione, e otteniamo:

 

P_5^{1,2,2} = \frac{5!}{1! \cdot 2! \cdot 2!} = \frac{120}{2 \cdot 2} = \frac{120}{4} = 30

 

Passiamo alla parola matematica. Qui le lettere sono n=10, di cui quelle che si ripetono sono:

 

n_1=2 lettere m;

 

n_2=3 lettere a;

 

n_3=2 lettere t.

 

Rimangono una lettera e, una lettera i e una lettera c. Come già osservato quest'ultime non hanno alcuna influenza sul conteggio delle permutazioni con ripetizione, dunque il numero totale di anagrammi della parola matematica è

 

P_{10}^{2,3,2} = \frac{10!}{2! \cdot 3! \cdot 2!} = \frac{3 \ 628 \ 800}{24} = 151 \ 200

 

 

2) Una moneta viene lanciata 9 volte. In quanti modi si può presentare una sequenza che contiene 6 teste e 3 croci?

 

Svolgimento: lo scopo è determinare il numero di modi in cui si può presentare una sequenza con n_1=6 teste e n_2=3 croci lanciando complessivamente n=9 volte una moneta.

 

Applichiamo la formula delle permutazioni con ripetizione

 

P_9^{6,3} = \frac{9!}{6! \cdot 3!} =

 

per facilitare i calcoli esplicitiamo 9! a numeratore

 

=\frac{9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6! \cdot 3!}=

 

il prodotto 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 è uguale a 6!, che possiamo semplificare con il 6! del denominatore

 

=\frac{9 \cdot 8 \cdot 7 \cdot 6!}{6! \cdot 3!} = \frac{9 \cdot 8 \cdot 7}{3!} = \frac{504}{6} = 84

 

 

3) Una partita di calcio termina 4 a 3. In quanti modi diversi possono essersi succedute le reti?

 

Svolgimento: il numero totale di reti è 7. Di queste, 4 sono state segnate da una squadra e le rimanenti 3 sono state segnate dall'altra.

 

Da ciò deduciamo che il numero di modi in cui possono essersi succedute le reti è uguale al numero di permutazioni con ripetizione di n=7 oggetti, di cui n_1=4 sono di un tipo e n_2=3 di un altro tipo:

 

P_7^{4,3} = \frac{7!}{4! \cdot 3!} = \frac{7 \cdot 6 \cdot 5}{3!} = \frac{210}{6} = 35

 

 


 

Si conclude qui la parte di Calcolo Combinatorio dedicata alle permutazioni, in cui abbiamo imparato a calcolare il numero di raggruppamenti che si possono formare con n oggetti, a seconda che essi siano tutti distinti tra loro oppure ve ne siano alcuni che si ripetono.

 

Nella prossima lezione introdurremo il concetto di disposizione. Nello specifico vedremo quanti sono i raggruppamenti ordinati di k elementi, distinti o meno, che si possono formare partendo da un insieme che ne contiene n.

 

 

Buon proseguimento su YouMath,

Giuseppe Carichino (Galois)

 

Lezione precedente.....Lezione successiva

 
 

Tags: cos'è una permutazione con ripetizione - calcolo delle permutazioni con ripetizione - formula per il calcolo del numero di permutazioni con ripetizione.