Permutazioni

Dati n oggetti tutti diversi (A, B, C, …) la scrittura P_n significa

• In quanti modi diversi si possono elencare?
• Quanti anagrammi si possono creare con n lettere diverse?

Prova…

Oggetti	Permutazioni	Quantità
{A}	A	1	= 1
{A, B}	AB BA	2 · 1	= 2
{A, B, C}	ABC ACB BAC BCA CAB CBA	3 · 2	= 6
{A, B, C, D}	ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA	4 · 6	= 24
{A, B, C, D, E}	A... B... C... D... E...	5 · 24	= 120

Lo schema precedente può essere interpretato come

Dati n oggetti

• in 1° posizione si può scegliere 1 tra gli n oggetti
• in 2° posizione si può scegliere 1 tra gli n-1 oggetti rimasti
• in 3° posizione si può scegliere 1 tra gli n-2 oggetti rimasti
• …
• in (n-1)-esima posizione si può scegliere tra i 2 oggetti rimasti
• in n-esima posizione si può scegliere l’unico elemento rimasto

---

Un altro modo per generare le permutazioni è il seguente

Oggetti	Permutazioni	Quantità
{A}	A	1	= 1
{A, B}	AB BA	1 · 2	= 2
{A, B, C}	ABC ACB CAB BAC BCA CBA	3 · 2	= 6
{A, B, C, D}	ABCD ABDC ADBC DABC ACBD ACDB ADCB DACB CABD CADB CDAB DCAB BACD BADC BDAC DBAC BCAD BCDA BDCA DBCA CBAD CBDA CDBA DCBA	4 · 6	= 24
{A, B, C, D, E}	ABCDE ... ABDCE ... ...	5 · 24	= 120

Lo schema precedente può essere interpretato come

• avendo un solo oggetto c’è un’unica scelta
  P₁ = 1
• siano x le permutazioni di (n-1) oggetti
  P_n-1 = x
• aggiungendo un oggetto n-esimo questo può essere concatenato a ognuna delle x permutazioni precedenti, di lunghezza (n-1), in n posizioni diverse ottenendo n*x nuove permutazioni.
  P_n = n · P_n-1

---

In entrambi i casi

• P₁ = 1
• P₂ = 2 · P₁ = 2 · 1
• P₃ = 3 · P₂ = 3 · 2 · 1
• …
• P_n-1 = (n-1) · P_n-2= (n-1) · (n-2) ··· 2 · 1
• P_n = n · P_n-1 = n · (n-1) · (n-2) ··· 2 · 1

Si riassume come

P_n = n! = n · (n-1) ··· 2 · 1