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

Combinazioni

La scrittura Cn,k significa

  • dati n oggetti tutti diversi (a, b, c, …)
  • in quanti modi si possono scegliere k oggetti
  • considerando uguali due sequenze con gli stessi oggetti?

oppure

  • Quante squadre di k elementi si possono comporre avendo a disposizione n persone?
  • Quante combinazioni semplici di n elementi di classe k?

Calcolo

0 1 2 3 4
1 1
{}
1
a
2 1
{}
2
a b
1
ab
3 1
{}
3
a b c
3
ab ac bc
1
abc
4 1
{}
4
a b c d
6
ab ac ad bc bd cd
4
abc abd acd bcd
1
abcd
5 1
{}
5
a b c d e
10
ab ac ad ae bc bd be
cd ce de
10
abc abd abe acd ace
ade bcd bce bde cde
5
abcd abce abde acde bcde
6 1
{}
6
a b c d e f
15
ab ac ad ae af bc bd
be bf cd ce cf de df
ef
20
abc abd abe abf acd ace
acf ade adf aef bcd bce
bcf bde bdf bef cde cdf
cef def
15
abcd abce abcf abde abdf
abef acde acdf acef adef
bcde bcdf bcef bdef cdef
7 1
{}
7
a b c d e f g
21
ab ac ad ae af ag bc
bd be bf bg cd ce cf
cg de df dg ef eg fg
35
abc abd abe abf abg acd
ace acf acg ade adf adg
aef aeg afg bcd bce bcf
bcg bde bdf bdg bef beg
bfg cde cdf cdg cef ceg
cfg def deg dfg efg
35
abcd abce abcf abcg abde
abdf abdg abef abeg abfg
acde acdf acdg acef aceg
acfg adef adeg adfg aefg
bcde bcdf bcdg bcef bceg
bcfg bdef bdeg bdfg befg
cdef cdeg cdfg cefg defg
8 1
{}
8
a b c d e f g h
28
ab ac ad ae af ag ah
bc bd be bf bg bh cd
ce cf cg ch de df dg
dh ef eg eh fg fh gh
56

70

Riepilogo

Quindi i valori di {n \choose k}, coefficiente binomiale n sopra k, sono

 

Dall’osservazione dello schema precedente risulta

  • {n \choose 0}=1
  • {n \choose 1}=n
  • {n \choose 2}=\frac{n(n-1)}{2}
  • {n \choose n-2}=\frac{n(n-1)}{2}
  • {n \choose n-1}=n
  • {n \choose n}=1

e

  • C_{n,k}={n \choose k}=\frac{n(n-1)\ ...\ (n-k+1)!}{k!}=\frac{n!}{k!(n-k)!}

Ancora

  1. {n \choose k}={n \choose n-k}
  2. {n \choose k} ={n-1 \choose k} +{n-1 \choose k-1}
  3. {n \choose k+1} ={n \choose k}\frac{n-k}{k+1}