Permutazioni

La scrittura Pn significa

  • dati n oggetti tutti diversi (A, B, C, …)
  • in quanti modi diversi si possono elencare?

oppure

  • Quanti anagrammi si possono creare con n lettere diverse?

Prova…

{A} A 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

{A} A 1
{A,B} AB
BA
1*2 = 2
{A,B,C} ABC ACB CAB
BAC BCA CBA
2*3 = 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
    P1 =1
  • siano x le permutazioni di (n-1) oggetti
    Pn-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.
    Pn =n*Pn-1

In entrambi i casi

  • P1 = 1
  • P2 = 2*P1 = 2*1
  • P3 = 3*P2 = 3*2*1
  • Pn-1 = (n-1)*Pn-2= (n-1)*(n-2)…2*1
  • Pn = n*Pn-1 = n*(n-1)*(n-2)…2*1

Si riassume come

P_n=n!=n\cdot(n-1)\ ...\ 2\cdot1

Notice: This work is licensed under a BY-NC-SA. Permalink: Permutazioni

Comments are closed.