Matematica discreta - i binomi

Matematica Discreta I

Binomi

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:

   

1

1

   

Riga 1 =1 =1

   

 

  1

0

  

  

2 2 2

  

  

Riga 2 =1 =2 =1

  

  

  

  

1

0 2

 

 

  



3 3

3 3

 

 

  



Riga 3 =1 =3 =3 =1

 

 

  



 

 

  



1

0 3

2

  

 

  

 

4 4 4 4 4

  

 

  

 

Riga 4 =1 =4 =6 =4 =1

  

 

  

 

  

 

  

 

1 3

0 2 4

Notiamo che in ogni riga ogni termine (tranne quelli estremi) si ottiene come somma dei 2



   

 



   

3 3

3

4

2 2 

   

 



   

termini che lo sovrastano nella riga superiore: per esempio = + , = +



   

 



   



   

 



   

1 1

2

2 2 2

Ciò dipende dalla seguente formula:

   

 

n - 1 n - 1

n

   

 

= +

   

   

 

  m - 1 m

m

Dimostrazione della formula:

Sviluppiamo il secondo membro, usando la formula alternativa per il calcolo del

coefficiente binomiale:

   

n - 1 n - 1 (n - 1)! (n - 1)! (n - 1)!

(n - 1)!

   

+ = + = +

   

   

m - 1 m (m - 1)!

[(n - 1) - (m - 1)]! m! (n - m - 1)! m! (n - m - 1)!

(m - 1)! (n - m)!

Per calcolare il comune denominatore delle 2 frazioni, è utile osservare che:

(m-1)!m=m!, (n-m-1)!(n-m)=(n-m)!

dunque il comune denominatore è m!(n-m)! e sviluppando i calcoli si ottiene:

  

  

n n

- -

1 1 (n (n

- 1)! - 1)!

m (m

(n - 1)! n

(n -

- m)

m)

  

 + = = =

  



  



m m

- 1 m!

m! (n

(n - -

m)! m)!