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 elementi di qualsiasi tipo. Si dicono permutazioni di tali elementi tutti i possibili raggruppamenti formati in modo che:

- ogni raggruppamento contenga tutti gli 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 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 elementi distinti. Il numero di permutazioni semplici si indica con ed è pari al fattoriale di

Permutazioni con ripetizione

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

Nello specifico supponiamo di avere elementi, di cui sono di un tipo, di un altro tipo, e così via fino a , con .

Il numero di permutazioni con ripetizione degli elementi si indica con $P_n^{n_1,n_2,...,n_k}$ ed è uguale al rapporto tra il fattoriale di e il prodotto dei fattoriali di

$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 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 ed è uguale al fattoriale di .

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 sono 4 e sono distinti tra loro. Per calcolare il numero di permutazioni usiamo la formula delle permutazioni semplici

e sostituiamo

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

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

Svolgimento: la successione è formata da 5 elementi, di cui 3 uguali alla lettera e 2 uguali alla lettera . 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

e sostituiamo

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)

..........

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