Coefficienti binomiali all`Esame di Stato

Quesiti per l’Esame di Stato
Il coefficiente binomiale
prof. Fabio Bonoli
6 maggio 2009
Sommario
IL COEFFICIENTE BINOMIALE
1. Permutazioni e fattoriale
2. Il coefficiente binomiale
3. Il binomio di Newton
4. Quesiti sul coefficiente binomiale
prof. Fabio Bonoli
6 maggio 2009
Permutazioni e fattoriale:
Quanti siano tutti i possibili anagrammi (anche privi di senso) di una
data parola?
con 3 lettere, per esempio ape, otteniamo i seguenti 6 anagrammi:

ape, aep, pae, pea, eap, epa
Con 4 lettere il numero di anagrammi cresce:
 rosa, roas, rsoa, rsao, raos, raso, orsa, oras, osra, osar, oars, oasr,
sroa, srao, sora, soar, sarò, saor, aros, arso, aors, aosr, asro, asor.
Sono 24. Se provassimo con 5 lettere otterremmo 120
prof. Fabio Bonoli
6 maggio 2009
Perché?
n scelte possibili per la prima lettera, a questo
punto restano n-1 scelte possibili per la
seconda, n-2 scelte possibili per la terza e cosi
via….
n  (n  1)  (n  2)  ... 1  n!
prof. Fabio Bonoli
6 maggio 2009
Definizione ricorsiva di n!
II fattoriale di un numero n può essere definito in modo ricorsivo:
1!=1
n! = n·(n-1)!
Il fattoriale cresce molto rapidamente:
 10! =3 628 000 e 70! è un numero di 101 cifre.
Risulta utile definire anche 0!; si pone per definizione 0!=1
e allora la definizione ricorsiva si modifica nel seguente modo:
0!=1
n! = n·(n-1)!
prof. Fabio Bonoli
6 maggio 2009
Il coefficiente binomiale e il teorema del binomio:
Sappiamo che
 (a + b)2 = a2 + 2ab + b2
 (a + b)3 =a3+3a2b+3ab2+b3.
Nel primo caso i coefficienti dello sviluppo sono (1, 2, 1), nel secondo
caso (1, 3, 3, 1).
Proseguendo nel calcolo delle successive potenze del binomio (a + b)
otteniamo:
 (a + b)4 =a4+4a3b+ 6a2b2 + 4ab3 + b4
 (a + b)5 =a5+5a4b+ 10a3b2 + 10a2b3+ 5ab4 + b5.
Sorge l'esigenza di generalizzare: qual è lo sviluppo di (a + b)n?
prof. Fabio Bonoli
6 maggio 2009
Poniamo un problema che apparentemente è molto lontano da questo.
Dato un insieme A che contiene n elementi; vogliamo sapere quanti
sono i sottoinsiemi distinti di A che contengono k elementi, per ogni
k compreso tra 0 e n.
Cominciamo a considerare un insieme di 2 elementi, per esempio {a,b}:
 - il numero di sottoinsiemi che hanno O elementi è 1: 
 - il numero di sottoinsiemi che hanno 1 elemento è 2: {a}, {b};
 - il numero di sottoinsiemi che hanno 2 elementi è 1: {a,b}.
Ritroviamo i numeri 1, 2, 1;
prof. Fabio Bonoli
6 maggio 2009
Vediamo cosa accade per gli insiemi di 3 elementi, come {a, b, c}:
 - il numero di sottoinsiemi che hanno O elementi è 1: 
 - il numero di sottoinsiemi che hanno 1 elemento è 3: {a}, {b}, {c}
 - il numero di sottoinsiemi che hanno 2 elementi è 3: {a,b} {a,c} {b,c};
 - il numero di sottoinsiemi che hanno 3 elementi è 1: {a,b,c}.
Ritroviamo la sequenza (1, 3, 3, 1), la stessa dello sviluppo di (a + b)3.
Non è difficile proseguire, e scoprire che anche per insiemi di 4
elementi si ritrovano le sequenze (1, 4, 6, 4, 1).
Le stesse sequenze si ottengono in due problemi differenti; è probabile
che ci sia per entrambi la stessa spiegazione.
 Il coefficiente di a2b2 nello sviluppo di (a+b)4 è 6;
 il numero di sottoinsiemi, aventi 2 elementi, di un insieme di 4
elementi, per esempio A = {a, b, c, d}, è anch'esso 6.
{a,b}, {a,c}, {a,d}, {b,c}, {b, d}, {c, d}.
prof. Fabio Bonoli
6 maggio 2009
Guardiamo questo esempio da un altro punto di vista.
In quanti diversi modi possiamo selezionare 2 elementi dall’insieme A =
{a, b, c, d}?
Abbiamo 4 scelte per il primo elemento,
e 3 per il secondo,
quindi 4 • 3 = 12 scelte.
Questo sarebbe il numero di differenti scelte ordinate di 2 elementi
presi da un insieme di 4 elementi. Ma a noi non interessa
l’ordinamento: il sottoinsieme che contiene, per esempio, gli
elementi a, d, è stato così contato più volte (2 volte):
{a,d,}, {d,a}.
prof. Fabio Bonoli
6 maggio 2009
Dunque dovremo dividere 12 per il numero dei diversi possibili
ordinamenti di 2 elementi, cioè, come abbiamo visto, per il numero
di permutazioni di 2 elementi, che è 2 ! = 2. In conclusione:
43
6
2!
come ci aspettavamo.
Quanti sono i sottoinsiemi di 4 elementi di un insieme di 6 elementi? Ci
sono 6 scelte possibili per il primo elemento, 5 per il secondo, 4 per
il terzo, 3 per il quarto, quindi 6 • 5 • 4 • 3 scelte ordinate, che
dobbiamo dividere per 4 ! :
6543
 15
4!
prof. Fabio Bonoli
6 maggio 2009
Possiamo concludere che il numero di sottoinsiemi aventi k elementi di
un insieme di n elementi oppure il numero di modi in cui seleziono k
elementi da un insieme di n oggetti è
n
n!
  
 k  k!(n  k )!
Naturalmente il numero di sottoinsiemi aventi 0 elementi è sempre 1,
cioè l'insieme vuoto; il corrispondente coefficiente binomiale
sarebbe
 n
n!
1
0!(n  0)!
  
 0
Questo risultato giustifica la precedente definizione: 0! = 1.
prof. Fabio Bonoli
6 maggio 2009
Torniamo al problema dello sviluppo di (a + b)n e mostriamo che è del
tutto equivalente al problema appena considerato. Che cosa
significa calcolare lo sviluppo di (a + b)n? Dobbiamo calcolare il
prodotto di n fattori
(a+b)(a+b) ... (a+b).
Se fosse n = 3, dovremmo moltiplicare ogni termine del primo monomio
per ogni termine del secondo, e ciascun risultato per ogni termine
del terzo; in tutto 8 monomi.
Ovvero da ogni binomio (a + b) prendiamo a caso un termine,
ottenendo così una terna di lettere, e facciamo questo in tutti i modi
possibili, che sono appunto 23 =8. Nel risultato, non ci interessa
l’ordine con cui si susseguono a e b, importa soltanto quante volte
compare a .
C'è un solo modo di ottenere aaa, ci sono invece 3 scelte diverse per
a2b: aab, aba, baa.
prof. Fabio Bonoli
6 maggio 2009
Ma questo è del tutto equivalente a determinare
quanti sottoinsiemi di 2 elementi abbia un insieme di 3 elementi
Ed è del tutto equivalente a determinare
in quanti modi posso selezionare 2 elementi da un insieme che ne
contiene 3.
Esempio: Determinare i coefficienti dello sviluppo di (a +b)6.
 6
 6  6! 6  5!
 6  6! 6  5!
 6  6!
   1 ;   

 6;   

 6 ;     1 ;
 0
 1  1!5! 5!
 5  5!1! 5!
 6  6!
 6  6! 6  5  4!
 6  6! 6  5  4!
 6  6! 6  5  4  3!
  

 15;   

 15;   

 20
 2  2!4! 2  4!
 4  4!2! 2  4!
 3  3!3! 3  2  3!
Quindi 1  a 6  6  a 5b  15  a 4b 2  20  a 3b 3  15  a 2b 4  6  ab 5  1 b 6
Quest'ultimo esempio mette in evidenza la simmetria dei coefficienti,
precedentemente osservata.
prof. Fabio Bonoli
6 maggio 2009
Il coefficiente binomiale
I numeri
Cn , k
n
n!

  
k!(n  k )!  k 
vengono anche detti “coefficienti binomiali”
Il coefficiente binomiale risponde alle domande:
1. "dati n oggetti, in quanti modi ne posso scegliere k?“
2. "dato un insieme di n oggetti, quanti sono i sottoinsiemi
composti da k elementi?“
3. “dato (a+b)n qual è il coefficiente di bk ?”
Proprietà
prof. Fabio Bonoli
n
   1 ;
0
n
 n 
n
n  n 
   n ; 
  n ;    1 ;    
 ;
1
 n  1
n
k  n  k 
 n   n  1  n  1
   
  

 k   k   k  1
6 maggio 2009
Teoremi
n  n 

k  N k  n    
k
n

k
  

Vale inoltre il seguente teorema relativo alla somma di coefficienti
binomiali:
n
 n 
  n  1 
1  n       
2
n2
 


n n n
 n   n  n
  
     2 n
          
 0  1  2
 n  2   n  1  n 
Dimostrazione La somma di tutti i coefficienti binomiali è uguale al
numero di tutti i sottoinsiemi di un insieme A di n elementi.
Ragioniamo in termini di scelte: un sottoinsieme S di A può essere
costruito scegliendo, per ogni elemento dell’insieme, se esso
appartenga oppure non appartenga a S; abbiamo 2 possibili scelte
per ciascun elemento di A, perciò 2n è il numero dei sottoinsiemi di
A.
prof. Fabio Bonoli
6 maggio 2009
Il binomio di Newton
Si chiama "binomio di Newton" la formula per lo sviluppo dell'n-esima
potenza di un binomio.
Per ogni n>1 risulta:
n n
a  b    a 
0
n
 n  n 1  n  n 2 2
 a b    a b   
1
 2
n
 n  nk k
   a b
k 0  k 
 n  n 1  n  n

a b   b 
 n  1
n
Una conseguenza immediata del teorema del binomio è una
dimostrazione alternativa del teorema sulla somma dei coefficienti
binomiali
n n n
 n   n  n
         
  
     (1  1) 2  2 n
 0 1  2
 n  2   n  1  n 
prof. Fabio Bonoli
6 maggio 2009
interpretiamo ogni numero per mezzo del corrispondente coefficiente
binomiale: per esempio consideriamo il numero 6 nell’ultima riga e i
due elementi della precedenti riga che gli «stanno sopra»:
6 =3 +3,
 4   3  3 
allora
    
 2
 
1  2
   
Questa apparente regolarità è effettivamente una proprietà dei
coefficienti binomiali, che possono essere definiti in termini di
coefficienti binomiali «più piccoli».
prof. Fabio Bonoli
6 maggio 2009
Teorema
 n   n  1  n  1
  

k  0 , n  2    
 k   k  1  k 
Dimostrazione E’ sufficiente utilizzare la definizione di coefficiente
binomiale:
 n  1  n  1
(n  1)!
(n  1)!

  
 


 k  1  k  (k  1)!(n  k )! (k )!(n  k  1)!
(n  1)!k  (n  1)!(n  k )

(n  k )!(k )!

prof. Fabio Bonoli
n
(n  1)!(k  n  k )
n!

  
k!(n  k )!
k!(n  k )!  k 
6 maggio 2009
n
 
k 
 n  1  n  1
     
 k   k  1
Abbiamo visto che il coefficiente binomiale ci indica il numero di
sottoinsiemi composti da k elementi presi da un insieme che ne
contiene n.
Nel primo addendo si considerano i sottoinsiemi composti da k
elementi nei quali non c’è l’elemento contrassegnato.
Il secondo addendo considera i sottoinsiemi composti da k elementi nei
quali c’è anche l’elemento contrassegnato.
prof. Fabio Bonoli
6 maggio 2009
2007 – Scientifico tradizionale
n
 n  2
n!
(n  2)!
  n  N , n  5  4 
4   15  
 15 

4!(n  4)!
3!(n  5)!
 4
 3 
4n  (n  1)  (n  2)!
(n  2)!
n2  n
 15 

 15 
4  3!(n  4)  (n  5)!
3!(n  5)! (n  4)
n 2  n  15  (n  4)  n 2  16n  60  0  n  10  n  6
2007 – Scientifico PNI supplettiva
 x  x  2
x!
( x  2)!
  x  N , x  3  5 
5   


3!( x  3)! 3!( x  1)!
 3  3 
5 x!( x  1)  ( x  2) ( x  2)  ( x  1)  x!


3!( x  1)!
3!( x  1)!
5( x  1)  ( x  2)  ( x  2)  ( x  1)  5 x 2  15 x  10  x 2  3 x  2 
1
2x2  9x  4  0   x  4  x  3  x  4
2
prof. Fabio Bonoli
6 maggio 2009
2008 – Scientifico tradizionale
n n n
Se  ,  ,   con n  3 sono in progressio ne aritmetica , qual è il valore di n?
 1  2  3
 n   n   n   n  n  (n  1)
n  (n  1)  (n  2) n  (n  1)
           
n 

 ...  n  7
2
6
2
 2  1  3  2
2008 – Scientifico tradizionale – Scuole italiane all’estero (Europa)
n
Quale significato attribuisci al simbolo  k 
Esiste un valor
e k per cui 10   
k
10 
 ?
 k  2
10   10 
10!
10!
   
 

 k!(10  k )!  (k  2)!(12  k )!
k!(10  k )! (k  2)!(12  k )!
 k   k  2
k  (k  1)  (k  2)!(10  k )!  (k  2)!(12  k )  (11  k )  (10  k )! ...  k  6
prof. Fabio Bonoli
6 maggio 2009
Oppure ricordando che
n  n 

k  N k  n    
k  n  k 
 10   10 

  
  10  k  k  2  k  6
10  k   k  2 
2008 – Scientifico tradizionale – Scuole italiane all’estero (Americhe)
Quante diagonali ha un poligono di 2008 lati?
 2008 
2008!
2008  2007
  2008 
C n , 2  n  
 2008 
 2008  2013020
2  2006!
2
 2 
oppure
n  (n  3) 2008  2005
da ogni verice partono (n - 3) diagonali

 2013020
2
2
prof. Fabio Bonoli
6 maggio 2009
2007 – Scientifico tradizionale – Scuole italiane all’estero (Europa)
Quante cifre ha 760 ?
Considero i numeri di 4 cifre, ad esempio, da 1000 a 9999. Le cifre
sono 4 in quanto il numero è  10 3 e  10 4
(una cifra per le unità, una per le decine, una per le centinaia e una per
le migliaia).

4  1  int(log
Pertanto log 10 7
60
10
n)
log 7 7 60
60


 60  log 10 7  50.7
log 7 10 log 7 10
Quindi il numero di cifre è 51.
2006 – Scientifico tradizionale Si dimostri che che la somma dei
coefficienti dello sviluppo di (a+b)n è uguale a 2n .
n n n
 n   n  n
         
  
     (1  1) 2  2 n
 0 1  2
 n  2   n  1  n 
prof. Fabio Bonoli
6 maggio 2009
2006 – Scientifico PNI
Bruno de Finetti (1906-1985), tra i più illustri matematici italiani del
secolo scorso, del quale ricorre quest’anno il centenario della
nascita, alla domanda: “che cos’è la probabilità?” era solito
rispondere: “la probabilità non esiste!”. Quale significato puoi
attribuire a tale risposta? E’ possibile collegarla ad una delle diverse
definizioni di probabilità che sono state storicamente proposte?
prof. Fabio Bonoli
6 maggio 2009