Matematica Discreta
Lezione del giorno 30 novembre 2009
Costruiremo ora una formula alternativa per il calcolo di
m
n
(ma all’inizio valida solo nel caso m≠0, m≠n).
Nella formula originale:
m n
=
m!1) m 2)....(n 1)(n
n(n
supponendo che sia m≠0, m≠n, moltiplichiamo numeratore e denominatore per (n-m)!, ottenendo la nuova formula:
m n
=
n(n1)...(nm!(nm-m)!1)[(n-m)!]=
n(n1)...(nmm!(n1)(n-m)!-m)(n-m-1)...1=
m)!
- (n m!
n!
Otteniamo dunque la formula alternativa:
m n
=
m!(n-m)!n!
(se m≠0, m≠n) .
Tale formula non ha senso nei casi m=0, m=n, perché contiene un termine 0! al quale non abbiamo attribuito significato. Ma possiamo dare significato alla formula anche nei casi m=0, m=n, definendo convenzionalmente 0!=1, per ritrovare i valori già noti:
0
n
=
0)!
- (n 0!
n!
=1
n
n
=
n)!
- (n n!
n!
=1
Utilizzando questa formula alternativa per il coefficiente binomiale, si ottiene il:
Teorema: Se n è un numero naturale, comunque preso un intero m con 0≤m≤n si ha:
m n
=
m-n n
Dimostrazione.
Usiamo la formula alternativa per sviluppare il secondo membro ed arrivare al primo:
m-n n
=
(n-m)![nn!-(n-m)]!=
(n-m)!n! m!=
m!(nn!-m)!=
m n
Dal Teorema precedente si ha che, fissato il numero naturale n e facendo variare m=0,1,…,n, i coefficienti binomiali:
0 n
,
1
n
,
2 n
, …… ,
2-n n
,
1-n n
,
n n
sono uguali a coppie simmetriche (equidistanti rispetto al “centro” della successione):
0 n
=
0 n
,
1
n
=
1-n n
,
2 n
=
2-n n
etc….
Esempio: se n=5 i coefficienti binomiali
m n
con m=0,1,2,3,4,5,sono uguali a coppie:
0 5
=1 ,
1
5
=5 ,
2 5
=10 ,
3 5
=10 ,
4 5
=5 ,
5 5
=1
Possiamo disporre i coefficienti binomiali in una struttura triangolare (detta triangolo di Tartaglia-Pascal) in cui in ogni riga si sistemano i coefficienti che hanno n fissato ed m variabile da 0 ad n. Per esempio le prime 4 righe del triangolo sono:
Riga 1
0 1
=1
1 1
=1
Riga 2
0 2
=1
1
2
=2
2 2
=1
Riga 3
0 3
=1
1
3
=3
2 3
=3
3 3
=1
Riga 4
0 4
=1
1
4
=4
2 4
=6
3 4
=4
4 4
=1
Notiamo che in ogni riga ogni termine (tranne quelli estremi) si ottiene come somma dei 2 termini
che lo sovrastano nella riga superiore: per esempio
2 3
=
1
2
+
2 2
,
2 4
=
1
3
+
2 3
Ciò non è casuale ma dipende dalla seguente formula (che ora dimostreremo):
m n
=
1-m 1-n
+
m
1-n
Dimostrazione della formula:
Sviluppiamo il secondo membro, usando la formula alternativa per il calcolo del coefficiente binomiale:
1-m 1-n
+
m
1-n
=
(m-1)![(n-1)-(m-1)]!1)!
-
(n
+
1)!
- m - (n m!
1)!
-
(n
=
m)!
- (n 1)!
- (m
1)!
-
(n
+
1)!
- m - (n m!
1)!
- (n