Matematica per le applicazioni I - calcolo combinatorio
Anteprima
ESTRATTO DOCUMENTO
Adolfo Scimone binomio di Newton pag 1
Formula di Newton per lo sviluppo del binomio
Siano a e b due numeri qualunque ed n un numero intero e positivo.
+ n
Ci proponiamo di calcolare la potenza ( a b )
Si ha:
n n n n n
+ = + + + + +
− − −
n n n 1 n 2 2 n 1 n
( a b ) a a b a b ... ab b
−
0 1 2 n 1 n
o brevemente
n
n
∑
+ = −
n n k k
( a b ) a b (1)
k
=
k 0
Dimostriamo la relazione mediante il principio di Maurolico (o principio di induzione)
a) p(1) è vera
b) Se p(n) è vera, dovrà essere vera anche p(n + 1)
Dim. =
a) per n 1 si ha
+ = +
a b a b =
per cui la (1) risulta vera per n 1 . + + +
n n 1
b)Supponiamo che la (1) sia vera per ( a b ) , dobbiamo provare che è vera anche per ( a b ) .
Avremo:
n n n n n
− − −
+ = + + = + + + + + + =
+ n n 1 n 2 2 n 1 n
n 1 n
( a b ) ( a b
) (
a b ) a a b a b ... ab b (
a b )
−
0 1 2 n 1 n
n n n n n n n
= + + + + + + + +
+ − − −
n 1 n n 1 2 2 n 1 n n n 1 2
a a b a b ... a b ab a b a b
−
0 1 2 n 1 n 0 1
n n n
+ + + +
− +
n 2 3 n n 1
a b ... ab b
−
2 n 1 n
Essendo + +
n n 1 n n 1
= =
ed +
0 0 n n 1
otteniamo: + +
n 1 n n n n n n n 1
− +
+ = + + + + + + +
+ + n n 1 2 n n 1
n 1 n 1
( a b ) a a b a b ab b
− +
0 1 0 2 1 n 1 n n 1
Per la legge di Stiefel
Adolfo Scimone binomio di Newton pag 2
− −
n 1 n 1 n
+ =
avremo
−
k k 1 k
+ +
n n n 1 n n n 1
+ = + =
1 0 1 2 1 2
e così via.
In definitiva otteniamo:
+ + + + +
n 1 n 1 n 1 n 1 n 1
+ = + + + + +
+ + − +
n 1 n 1 n n 1 2 n n 1
( a b ) a a b a b ... ab b
+
0 1 2 n n 1
quindi p(n + 1) risulta vera. ¥
∈
Pertanto la (1) risulta valida per ogni n .
Considerazioni sulla formula
+
i) Il numero degli addendi nel secondo membro è n 1
ii) In questi addendi gli esponenti della lettera a vanno diminuendo di uno qualunque al
successivo, mentre gli esponenti della lettera b vanno sempre aumentando di una unità
nel suddetto passaggio
iii) I coefficienti dei termini estremi ed i coefficienti dei termini equidistanti dagli estremi
n n n n n n
= = =
sono tra loro uguali. Si ha ; , , ……
− −
0 n 1 n 1 2 n 2
Questa osservazione ci risparmia il calcolo di molti coefficienti: se n è dispari e quindi il
+
n 1
+
numero n 1 dei termini dello sviluppo è pari, basta calcolare i primi coefficienti;
2
n
+ +
se invece n è pari e quindi n 1 dispari, basta calcolare i primi 1 coefficienti
2
iv) Il coefficiente di un termine qualunque dello sviluppo, a partire dal secondo, si ottiene
moltiplicando il coefficiente del termine precedente per l’esponente che in esso ha la
lettera a, e dividendo il risultato ottenuto per l’esponente della lettera b aumentato di una
−
n n n k
=
unità. Infatti si ha + +
k 1 k k 1
Calcolo Combinatorio Adolfo Scimone pag 1
Calcolo combinatorio
Consideriamo un insieme di n oggetti di natura qualsiasi. Indicheremo questi oggetti con
a , a ,..., a .
1 2 n
Con questi n oggetti si vogliono formare dei gruppi, ciascuno formato da uno stesso numero k di
≤
oggetti con k n .
Disposizioni semplici di n oggetti
Definizione: Dati n oggetti e detto k un numero intero positivo minore o uguale a n, si chiamano
disposizioni semplici di questi n oggetti presi a k a k o della classe k, tutti i gruppi che si possono
formare con gli n oggetti dati in modo che ogni gruppo contenga soltanto k degli oggetti dati, e che
due gruppi qualunque differiscano fra loro o per qualche oggetto, oppure per l’ordine con cui gli
oggetti sono disposti.
Esempio – Dati tre oggetti, indicati con le lettere A,B,C, le disposizioni di classe 2 sono tutte le file
realizzabili usando ogni volta due delle tre lettere:
AB, BA, AC, CA, BC, CB
Si tratta, quindi di sei file possibili.
Indichiamo quindi con D il numero delle disposizioni semplici di n oggetti di classe k.
n , k
Teorema – Il numero delle disposizioni semplici di n oggetti di classe k è dato da:
= − − − + − −
D n ( n 1)( n 2).....(
n k 2)(
n k 1)
n , k
cioè D è uguale al prodotto dei k numeri consecutivi decrescenti a partire da n.
n , k
Dimostrazione Gli n elementi diversi
a , a ,..., a
1 2 n
presi ad uno ad uno danno luogo, ovviamente, ad n disposizioni di classe uno
=
D n (1)
n ,1
Per formare tutti i gruppi di classe 2 consideriamo, successivamente, ciascun gruppo di classe 1 e,
−
di seguito poniamo uno alla volta ciascuno degli n 1 elementi estranei al gruppo considerato. Ogni
−
gruppo di classe 1 genera così n 1 gruppi di classe 2.
Possiamo quindi scrivere
= −
D D ( n 1) (2)
n ,2 n ,1
Per formare tutti i gruppi di classe 3, consideriamo, successivamente, ciascun gruppo di classe 2 e ,
−
di seguito, poniamo uno alla volta ciascuno degli n 2 elementi estranei al gruppo considerato.
−
Ogni gruppo di classe 2 genera così n 2 gruppi di classe 3. Possiamo quindi scrivere
= −
D D ( n 2) (3)
n ,3 n ,2 − −
e così via. Per formare i gruppi di classe k 1 consideriamo ciascun gruppo di classe k 2 e
− − = − +
poniamo uno alla volta ciascuno degli n ( k 2) n k 2 elementi estranei al gruppo
considerato. Avremo quindi:
= − +
D ( n k 2) D (k-1)
− −
n , k 1 n , k 2 −
Per formare infine tutti i gruppi di classe k, consideriamo ciascun gruppo di classe k 1 e poniamo,
− − = − +
di seguito, uno alla volta ciascuno degli n ( k 1) n k 1 elementi estranei al gruppo
considerato.
Avremo
= − +
D ( n k 1) D (k)
−
n , k n , k 1
Moltiplicando membro a membro le k relazioni (1), (2),……,(k) precedenti otteniam
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Sara F di informazioni apprese con la frequenza delle lezioni di Matematica per le applicazioni I e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Firenze - Unifi o del prof Gori Franco.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato
