Permutazioni

Una permutazione è il risultato di uno scambio dell'ordine degli elementi di una sequenza, ossia è uno dei possibili modi per ordinare elementi di qualsiasi tipo. Si distinguono tre tipi di permutazioni: le permutazioni semplici, le permutazioni con ripetizione e le permutazioni circolari.

 

Nelle precedenti lezioni abbiamo introdotto i concetti di fattoriale e di coefficiente binomiale. Con questi prerequisiti abbiamo tutto quello che ci serve per passare al cuore del corso sul Calcolo Combinatorio: iniziamo dallo studio delle permutazioni, per poi passare alle disposizioni e infine alle combinazioni.

 

In questo frangente ci limitiamo a vedere cos'è una permutazione e a passare in rassegna i vari tipi di permutazioni, proponendo una breve spiegazione, la formula di calcolo e qualche esempio di applicazione. Nelle lezioni successive tratteremo le permutazioni semplici e le permutazioni con ripetizione nel dettaglio, spiegando da dove derivano le rispettive formule e proponendo numerosi esempi.

 

Definizione di permutazione

 

Per fornire la definizione di permutazione consideriamo n elementi di qualsiasi tipo. Si dicono permutazioni di tali elementi tutti i possibili raggruppamenti formati in modo che:

 

- ogni raggruppamento contenga tutti gli n elementi;

 

- ciascuno di tali raggruppamenti differisca dagli altri per l'ordine con cui gli elementi si susseguono.

 

Vediamo subito un esempio. Le possibili permutazioni degli elementi dell'insieme A=\{a,b,c\} sono:

 

\\ abc \ \ ; \ \ acb \\ \\ bac \ \ ;\ \ bca \\ \\ cab \ \ ; \ \ cba

 

e si differenziano per l'ordine con cui i tre elementi si presentano.

 

Tipi di permutazioni

 

Possiamo distinguere tre tipi di permutazioni: le permutazioni semplici, le permutazioni con ripetizione e le permutazioni circolari.

 

Se gli n elementi di partenza sono distinti tra loro si parla di permutazioni semplici, in caso contrario di permutazioni con ripetizione.

 

Le permutazioni circolari sono un tipo particolare di permutazione semplice, in cui gli elementi sono disposti in modo circolare e non è possibile distinguere il primo dall'ultimo elemento.

 

Non perdiamoci in ulteriori preamboli. Nel contesto delle permutazioni ciò che conta è saperle distinguere (in modo da poterle utilizzare nelle applicazioni combinatorie) e saperne calcolare il numero a partire dal numero di elementi assegnati. Passiamo quindi alle definizioni e alle formule con cui si calcolano il numero di permutazioni semplici, il numero di permutazioni con ripetizione e il numero di permutazioni circolari.

 

Permutazioni semplici (dette anche permutazioni senza ripetizione)

 

Si dicono permutazioni semplici i possibili modi per ordinare totalmente n elementi distinti. Il numero di permutazioni semplici si indica con P_n ed è pari al fattoriale di n

 

P_n=n!

 

 

Permutazioni con ripetizione

 

Si dicono permutazioni con ripetizione i possibili modi per ordinare totalmente n elementi di cui alcuni sono ripetuti due o più volte.

 

Nello specifico supponiamo di avere n elementi, di cui n_1 sono di un tipo, n_2 di un altro tipo, e così via fino a n_k, con n_1+n_2+...+n_k=n.

 

Il numero di permutazioni con ripetizione degli n elementi si indica con P_n^{n_1,n_2,...,n_k} ed è uguale al 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

 

 

Permutazioni circolari

 

Si dicono permutazioni circolari tutti i possibili modi per ordinare totalmente n elementi distinti, da disporre in modo circolare e in cui non si può distinguere la prima dall'ultima posizione. Il numero di permutazioni circolari si indica con P_n^c ed è uguale al fattoriale di n-1.

 

P_n^c = (n-1)!

 

Esempi sul calcolo del numero di permutazioni

 

1) Calcolare il numero di permutazioni degli elementi dell'insieme E=\{a,b,c,d\}.

 

Svolgimento: gli elementi di E sono 4 e sono distinti tra loro. Per calcolare il numero di permutazioni usiamo la formula delle permutazioni semplici

 

P_n=n!

 

e sostituiamo n=4

 

P_4 = 4! = 4 \cdot 3 \cdot 2 \cdot 1 = 24

 

 

2) Calcolare il numero di permutazioni degli elementi della successione a,b,a,b,a.

 

Svolgimento: la successione è formata da 5 elementi, di cui 3 uguali alla lettera a e 2 uguali alla lettera b. Applichiamo allora la formula delle permutazioni con ripetizione

 

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

 

ed effettuiamo le seguenti sostituzioni

 

n=5 \ \ ; \ \ n_1=3 \ \ ; \ \ n_2=2

 

da cui ricaviamo

 

P_5^{3,2} = \frac{5!}{3! \cdot 2!} = \frac{120}{6 \cdot 2} = \frac{120}{12} = 10

 

 

3) In quanti modi sei persone possono sedersi attorno a una tavola rotonda con sei sedie non numerate?

 

Svolgimento: l'insieme da cui partire è formato da 6 elementi, ossia le sei persone che devono occupare il posto attorno al tavolo. Poiché il tavolo è rotondo e i posti a sedere non sono numerati, per calcolare il numero di modi in cui si possono sedere usiamo la formula delle permutazioni circolari

 

P_n^c = (n-1)!

 

e sostituiamo n=6

 

P_6^c = (6-1)! = 5! = 120

 

 


 

Siamo giunti al termine di questa lezione. Nelle successive spiegheremo come si ricavano le formule per il calcolo delle permutazioni semplici e delle permutazioni con ripetizione, e proporremo altri esempi ed esercizi svolti.

 

Nel frattempo vi raccomandiamo di dare un'occhiata alla scheda correlata di esercizi risolti sulle permutazioni. ;)

 

 

Buon proseguimento su YouMath,

Giuseppe Carichino (Galois)

 

Lezione precedente.....Esercizi correlati.....Lezione successiva

 
 

Tags: cos'è una permutazione - tipi di permutazioni - numero di permutazioni - differenza tra permutazioni semplici, permutazioni con ripetizione e permutazioni circolari.