conta il numero delle combinazioni semplici di n elementi presi ad m ad m, o equivalentemente il numero dei sottoinsiemi di cardinalità m contenuti in un insieme di cardinalità n.

Matematica Discreta I

Lezione del giorno 15 dicembre 2008 Proprietà del coefficiente binomiale

Abbiamo visto che, fissati i numeri naturali n,m, (con mn) il coefficiente binomiale

_



 



 m

n

conta il numero delle combinazioni semplici di n elementi presi ad m ad m, o equivalentemente il numero dei sottoinsiemi di cardinalità m contenuti in un insieme di cardinalità n.

Fissato il numero n, i valori possibili di m sono m=1,2….,n.

Ma tenendo conto del significato insiemistico, possiamo estendere per convenzione il valore del coefficiente binomiale anche al caso m=0, definendo

_



 



 0

n

=1, coerentemente con l’osservazione che esiste 1 solo sottoinsieme di cardinalità 0 (quello vuoto) contenuto in un insieme di cardinalità n.

Dunque i possibili coefficienti binomiali con n fissato sono i seguenti:



 



 0

n

=1,

_



 



 1

n

, …….,

_



 



 1 - n

n

,

_



 



 n n

.

Notare che si ha

_



 



 n n

=

m!

1) n 2)....(n 1)(n

n(n   

=

n!

n!

=1 , quindi i 2 valori “estremi” (il primo e l’ultimo) sono ambedue uguali a 1.

Costruiamo 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(n1)...(n}_m!^_(n^m_-m)!^{1)[(n-m)!]}

=

^{n(n1)...(nm}_m!^_(n¹⁾⁽ⁿ_-m)!^{-m)(n-m-1)...1}

=

m)!

- (n m!

n!

Otteniamo dunque la formula alternativa:

 

 



 m n

=

_m!(n^n!_-m)!

(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^n!_-0)!

=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)![n^n!_-(n-m)]!

=

_(n-m)!^n! _m!

=

_m!(n^n!_-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

, 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ò dipende dalla seguente formula:

 

 



 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)]!

+

_m!(n⁽ⁿ_-^-_m^1)!_-1)!

=

_(m-⁽ⁿ_1)!^-_(n^1)!_-m)!

+

_m!(n⁽ⁿ_-^-_m^1)!_-1)!

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:

 

 



 1-m 1-n

+ 



 



 m

1-n

=

^(n-1)!m_m!^_(n⁽ⁿ_-^-_m)!^1)!(n-m)

=

^(n-1)!_m!^(m_(n-^_m)!^n-m)

=

=

_m!⁽ⁿ_(n^-1)!_-m)!ⁿ

=

_m!(n^n!_-m)!

=

 

 



 m n

.

La formula precedente permette di ricavare i termini di un riga del triangolo di Tartaglia-Pascal (tranne i 2 estremi che sono sempre uguali ad 1) conoscendo quelli della riga superiore e sommandoli a 2 a 2. Per esempio dalla conoscenza della riga numero 4:

 

 



 0 4

=1

 

 



 1

4

=4

 

 



 2 4

=6

 

 



 3 4

=4

 

 



 4 4

=1

si possono ricavare subito i termini della riga numero 5:

 

 



 0 5

=1

 

 



 1

5

=1+4=5

 

 



 2 5

=4+6=10

 

 



 3 5

=6+4=10

 

 



 4 5

=4+1=5

 

 



 5 5

=1

e poi quella della riga 6 e così via.

Sviluppo della potenza di un binomio secondo Newton

Se a,b sono numeri reali >0, sono ben note le formule per calcolare il quadrato e il cubo del binomio (a+b):

(a+b)

²

= a

²

+2ab+b

²

(a+b)

³

= a

³

+3a

²

b+3ab

²

+b

³

Esaminando la riga numero 2 e la riga numero 3 del triangolo di Tartaglia-Pascal, possiamo scrivere le precedenti formule anche nel modo seguente:

(a+b)

²

=

 

 



 0 2

a

²

+

 

 



 1

2

ab+ 



 



 2 2

b

²

(a+b)

³

=

 

 



 0 3

a

³

+

 

 



 1

3

a

²

b+

 

 



 2 3

ab

²

+

 

 



 3 3

b

³

Queste formule sono un caso particolare di una formula generale (dovuta a Newton) che permette di calcolare (per ogni numero naturale n) la potenza (a+b)

ⁿ

, considerando tutti i prodotti delle potenze di base a per le potenze di base b (in cui gli esponenti di a decrescono da n a 0 e quelli di base b crescono da 0 a n), moltiplicando tali prodotti ordinatamente per gli elementi della riga numero n del triangolo di Tartaglia-Pascal e sommando i risultati:

(a+b)

ⁿ

=

 

 



 0 n

a

ⁿ

+

 

 



 1

n

a

^n-1

b+

 

 



 2 n

a

^n-2

b

²

+……+

 

 



 2-n n

a

²

b

^n-2

+

 

 



 1-n n

ab

^n-1

+

 

 



 n n

b

ⁿ

Dimostrazione della formula di Newton:

Si usa il principio di induzione. Per n=1 la formula dà l’eguaglianza:

(a+b)

¹

=

 

 



 0 1

a

¹

+

 

 



 1 1

b

¹

che é banalmente vera in quanto

 

 



 0 1

= 



 



 1 1

=1 .

Supponiamo vera la formula per n, e dimostriamola vera per n+1: la tesi è dunque la seguente

(a+b)

ⁿ⁺¹

=

 

 



  0

1n

a

ⁿ⁺¹

+

 

 



  1

1n

a

ⁿ

b+

 

 



  2

1n

a

^n-1

b

²

+……+

 

 



  1-n

1n

a

²

b

^n-1

+

 

 



  n

1n

ab

ⁿ

+

 

 







 1n 1n

b

ⁿ⁺¹

(*)

Sfruttiamo l’identità (a+b)

ⁿ⁺¹

=(a+b)(a+b)

ⁿ

e l’ipotesi che la formula è vera per n, ottenendo, per la proprietà distributiva:

(a+b)

ⁿ⁺¹

=(a+b)

ⁿ

(a+b)=

=(a+b)[

 

 



 0 n

a

ⁿ

+

 

 



 1

n

a

^n-1

b+

 

 



 2 n

a

^n-2

b

²

+……+

 

 



 2-n n

a

²

b

^n-2

+

 

 



 1-n n

ab

^n-1

+

 

 



 n n

b

ⁿ

]=

= 



 



 0 n

a

ⁿ⁺¹

+

 

 



 1

n

a

ⁿ

b+

 

 



 2 n

a

^n-1

b

²

+……..…+

 

 



 2-n n

a

³

b

^n-2

+

 

 



 1-n n

a

²

b

^n-1

+

 

 



 n n

ab

ⁿ

+

+ 



 



 0 n

a

ⁿ

b+

 

 



 1

n

a

^n-1

b

²

+

 

 



 2 n

a

^n-2

b

³

+…………+

 

 



 2-n n

a

²

b

^n-1

+

 

 



 1-n n

ab

ⁿ

+

 

 



 n n

b

ⁿ⁺¹

=

= 



 



 0 n

a

ⁿ⁺¹

+[

 

 



 1

n

+ 



 



 0 n

] a

ⁿ

b+[

 

 



 2 n

+ 



 



 1

n

] a

^n-1

b

²

+...+[

 

 



 n n

+ 



 



 1-n n

] ab

ⁿ

+

 

 



 n n

b

ⁿ⁺¹

e si ottiene, come si voleva, il secondo membro della (*), tenendo conto che

 

 



 0 n

=1= 



 



  0

1n

, 



 



 n n

=1= 



 







 1n 1n

, ed applicando la formula (già dimostrata)

 

 



 m n

= 



 



 1-m 1-n

+ 



 



 m

1-n

(da cui si ottiene

sostituendo n con n+1 ed m con 1:

 

 



  1

1n

= 



 



 0 n

+ 



 



 1

n

; poi sostituendo n con n+1 ed con 2:

 

 



  2

1n

=

 

 



 1

n

+ 



 



 2 n

etc…).

Principio dei cassetti.

Si basa sul seguente risultato di insiemistica: se A,B sono insiemi finiti, con A=n, B=m, e se n>m , comunque data una funzione f: A → B, esistono sempre almeno 2 elementi diversi in A che hanno in B lo stesso corrispondente mediante f (tale risultato è ovvio perché sappiamo che, se n>m, la funzione f certamente non è iniettiva).

Se pensiamo ad A come un insieme di n “oggetti”, a B come un insieme di m “cassetti”, e alla funzione f come un modo di inserire ogni oggetto in un cassetto, il principio afferma semplicemente che se il numero di oggetti è maggiore di quello dei cassetti, certamente esistono almeno 2 oggetti diversi che saranno inseriti nello stesso cassetto.

Applicazioni del principio dei cassetti:

1) Il paradosso delle “strette di mano”.

Supponiamo che A sia un insieme di n persone che si riuniscono, e che ognuna stringa la mano ad alcune altre (al limite anche a nessuna o a tutte le altre). Si può allora concludere con certezza che esistono almeno 2 persone diverse che hanno stretto la mano allo stesso numero di persone.

Infatti se B è l’insieme dei numeri interi da 0 ad (n.-1), possiamo definire una funzione f: A → B, associando ad ogni persona il numero di strette di mano. Ovviamente però non può avvenire contemporaneamente che i valori 0 e (n-1) siano corrispondenti di elementi di A (se esiste una persona che ha stretto le mani a tutte le altre, non ne esiste una che non ha stretto le mani a nessuno). Quindi possiamo restringere il codominio B, sostituendolo con un insieme C ottenuto togliendo da B quel numero (0 oppure (n-1)) che non è corrispondente di nessun elemento di A.

Otteniamo così una funzione f: A → C, dove A=n, C=n-1<n: applicando il principio dei cassetti si ha la tesi.

2) Il problema del “bersaglio”.

Si supponga di colpire con 101 colpi (tutti a segno) un bersaglio quadrato con il lato di lunghezza 70 cm. Allora certamente esistono almeno 2 colpi sul bersaglio che distano meno di 10 cm.

Infatti basta suddividere il bersaglio in 100 quadrati, ognuno con il lato di lunghezza 7 cm.,

considerare l’insieme A dei 101 colpi e l’insieme B dei 100 quadrati, e definire poi la funzione

f: A→ B che associa ad ogni colpo di A il quadrato in cui esso cade. Per il principio dei cassetti

esistono almeno 2 colpi che cadono nello stesso quadrato, e geometricamente la loro distanza non è

superiore alla lunghezza della diagonale che è uguale a

7 2

cioè circa 9,9 cm.