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 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 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 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 .

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 oppure .

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

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

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

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

In sintesi le permutazioni con ripetizione degli elementi sono:

Calcolo del numero di permutazioni con ripetizione

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

Il numero di permutazioni con ripetizione degli elementi così assegnati si indica con , ed è dato dal rapporto tra il fattoriale di e il prodotto dei fattoriali di

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 , e verifichiamo che sono proprio 3.

Vi sono elementi, di cui:

uguali alla lettera ;

uguali alla lettera .

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

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 elementi, di cui di tipo 1, di tipo 2, ..., ed di tipo k, con , è dato da

Dimostrazione

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

Il numero di modi con cui si possono riempire le 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  su , indicato con , rappresenta il numero di modi in cui elementi possono essere scelti tra , a prescindere dall'ordine.

Passo 1) Scegliamo caselle in cui disporre gli elementi di tipo 1. Tale scelta può essere fatta in modi.

Passo 2) Tra le caselle rimaste libere, scegliamo caselle in cui disporre gli elementi di tipo 2. Ciò può essere fatto in modi.

Passo 3) Tra le caselle rimaste libere, scegliamo caselle in cui disporre gli elementi di tipo 3. Ciò si può fare in modi.

Passo k) Reiterando il procedimento arriviamo all'ultimo passo. Tra le caselle rimaste libere scegliamo caselle in cui disporre gli elementi di tipo k. Ciò si può fare in modi.

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

esplicitiamo i coefficienti binomiali

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

In conclusione:

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

e osserviamo che qualsiasi elemento presente volta dà un contributo pari a , 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 , che evidentemente non sono tutte distinte tra loro. Vi sono infatti:

lettera ,

lettere ,

lettere ,

per un totale di elementi da permutare.

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

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

lettere ;

lettere ;

lettere .

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

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 teste e croci lanciando complessivamente volte una moneta.

Applichiamo la formula delle permutazioni con ripetizione

per facilitare i calcoli esplicitiamo 9! a numeratore

il prodotto è uguale a 6!, che possiamo semplificare con il 6! del denominatore

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 oggetti, di cui sono di un tipo e di un altro tipo:

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 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 elementi, distinti o meno, che si possono formare partendo da un insieme che ne contiene .

È tutto! A proposito, non perdetevi la scheda correlata di esercizi svolti sulle permutazioni! ;)

Buon proseguimento su YouMath,

Giuseppe Carichino (Galois)

..........

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