Post on 21-Feb-2021
transcript
LEZIONE 5: CALCOLOCOMBINATORIO
Giacomo Tommei
e-mail: tommei@dm.unipi.it
web: www.dm.unipi.it/∼tommei
Ricevimento: Martedi 16 - 18Dipartimento di Matematica, piano terra, studio 126
31 Ottobre 2012
Cos’e il calcolo combinatorio?
Il calcolo combinatorio e uno strumento che ci permette dicontare i modi nei quali raggruppiamo, secondo opportuneregole, elementi di un insieme finito.
Esempi
In quanti modi posso combinare 6 canzoni in gruppi di 4? E se lecanzoni fossero 10? Oppure 20?
Ad una corsa partecipano 15 persone. Quanti possibili podipossono verificarsi? Quanti sono gli ordini di arrivo possibili?
Quanti sono i possibili pin di un bancomat formati da 5 cifre?
Ho un gruppo di 7 persone e ne devo scegliere 3. In quanti modiposso farlo?
Giacomo Tommei Calcolo combinatorio
Disposizioni senza ripetizione
EsercizioQuanti numeri di tre cifre distinte si possono formare con le cifre2, 4, 6, 8, 9?
SoluzionePosso scegliere la prima cifra in 5 modi diversi, la seconda in 4 e laterza in 3:
# {num. 3 cifre distinte} = 5 · 4 · 3 = 60
Quello che abbiamo fatto e stato disporre un insieme finito dielementi in un certo numero di posti (numero di posti minore o ugualedel numero di elementi) col vincolo che gli elementi non si potesseroripetere.
Giacomo Tommei Calcolo combinatorio
Disposizioni senza ripetizione
EsercizioQuanti numeri di tre cifre distinte si possono formare con le cifre2, 4, 6, 8, 9?
SoluzionePosso scegliere la prima cifra in 5 modi diversi, la seconda in 4 e laterza in 3:
# {num. 3 cifre distinte} = 5 · 4 · 3 = 60
Quello che abbiamo fatto e stato disporre un insieme finito dielementi in un certo numero di posti (numero di posti minore o ugualedel numero di elementi) col vincolo che gli elementi non si potesseroripetere.
Giacomo Tommei Calcolo combinatorio
Disposizioni senza ripetizione
Dato un insieme contenente n elementi distinti, si chiamadisposizione semplice degli n elementi , presi k a k, o di classe k(k ≤ n), un gruppo ordinato di k degli n elementi dell’insieme.
Il numero delle disposizioni semplici di n elementi distinti, presi k a k,e uguale al prodotto di k numeri interi consecutivi decrescenti, deiquali il primo e n:
Dn,k = n (n− 1) (n− 2) . . . (n− k + 1)
Giacomo Tommei Calcolo combinatorio
Disposizioni senza ripetizione
EsercizioQuanti sono i numeri di 3 cifre tutte distinte?
SoluzioneLe cifre a nostra disposizione sono dieci (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) e ledisposizioni di 10 elementi di classe 3 sono date da:
D10,3 = 10 · 9 · 8 = 720
Tra queste pero figurano anche le sequenze di tre cifre la cui cifradelle centinaia e 0, che naturalmente non rappresentano un numero ditre cifre. Dalle disposizioni D10,3 dobbiamo quindi sottrarre
D9,2 = 9 · 8 = 72
che rappresenta la cardinalita dell’insieme dei numeri composti da duecifre distinte. La soluzione finale e quindi:
D10,3 −D9,2 = 720− 72 = 648
Giacomo Tommei Calcolo combinatorio
Disposizioni senza ripetizione
EsercizioQuanti sono i numeri di 3 cifre tutte distinte?
SoluzioneLe cifre a nostra disposizione sono dieci (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) e ledisposizioni di 10 elementi di classe 3 sono date da:
D10,3 = 10 · 9 · 8 = 720
Tra queste pero figurano anche le sequenze di tre cifre la cui cifradelle centinaia e 0, che naturalmente non rappresentano un numero ditre cifre. Dalle disposizioni D10,3 dobbiamo quindi sottrarre
D9,2 = 9 · 8 = 72
che rappresenta la cardinalita dell’insieme dei numeri composti da duecifre distinte. La soluzione finale e quindi:
D10,3 −D9,2 = 720− 72 = 648
Giacomo Tommei Calcolo combinatorio
Disposizioni con ripetizione
EsercizioQuante sono le targhe di tre lettere formate usando l’insieme{A,B,C,D,E}?
SoluzioneDobbiamo costruire targhe formate da tre lettere avendone adisposizione cinque e soprattutto, a differenza degli eserciziprecedenti, potendo ripetere la stessa lettera (e ammessa, ad esempio,la targa BBB). Ragionando allo stesso modo, posso scegliere la primalettera in 5 modi diversi, la seconda ancora in 5 e la terza pure in 5; ilnumero totale di targhe e allora dato da:
# {targhe} = 5 · 5 · 5 = 53 = 125
Giacomo Tommei Calcolo combinatorio
Disposizioni con ripetizione
EsercizioQuante sono le targhe di tre lettere formate usando l’insieme{A,B,C,D,E}?
SoluzioneDobbiamo costruire targhe formate da tre lettere avendone adisposizione cinque e soprattutto, a differenza degli eserciziprecedenti, potendo ripetere la stessa lettera (e ammessa, ad esempio,la targa BBB). Ragionando allo stesso modo, posso scegliere la primalettera in 5 modi diversi, la seconda ancora in 5 e la terza pure in 5; ilnumero totale di targhe e allora dato da:
# {targhe} = 5 · 5 · 5 = 53 = 125
Giacomo Tommei Calcolo combinatorio
Disposizioni con ripetizione
Dato un insieme contenente n elementi distinti, si chiamadisposizione con ripetizione degli n elementi , presi k a k, con kintero qualunque, un gruppo ordinato di k degli n elementi,considerando che uno stesso elemento possa figurare nel gruppo fino ak volte.
Il numero delle disposizioni con ripetizione di n elementi distinti, presik a k, e uguale alla potenza di base n ed esponente k:
Drn,k = nk
Giacomo Tommei Calcolo combinatorio
Permutazioni
EsercizioTrova il numero di anagrammi che si possono formare con la parola“zero”.
SoluzioneCon anagrammi intendiamo anche quelli privi di significato, adesempio un possibile anagramma di “zero” e “ezro”. Abbiamo adisposizione quattro lettere e dobbiamo riposizionarle in quattro posti,naturalmente non ripetendole; di conseguenza il numero cercato e
# {anagrammi} = 4 · 3 · 2 · 1 = 24
Giacomo Tommei Calcolo combinatorio
Permutazioni
EsercizioTrova il numero di anagrammi che si possono formare con la parola“zero”.
SoluzioneCon anagrammi intendiamo anche quelli privi di significato, adesempio un possibile anagramma di “zero” e “ezro”. Abbiamo adisposizione quattro lettere e dobbiamo riposizionarle in quattro posti,naturalmente non ripetendole; di conseguenza il numero cercato e
# {anagrammi} = 4 · 3 · 2 · 1 = 24
Giacomo Tommei Calcolo combinatorio
Permutazioni
Dato un insieme contenente n elementi distinti, si chiamapermutazione di n elementi una disposizione semplice degli nelementi, presi “n a n”.
In parole piu semplici, le permutazioni di n elementi distinti di uninsieme sono tutti i gruppi di n elementi formati con gli elementidell’insieme e che differiscono tra loro solo per l’ordine degli elementi.Il numero delle permutazioni di n elementi e dato da
Pn = Dn,n = n (n− 1) (n− 2) . . . 2 · 1 = n!
Attenzione: il simbolo ! indica il fattoriale del numero naturale n:n! e il prodotto dei primi n numeri naturali escluso lo zero. Se n = 1 on = 0 si pone per definizione 1! = 1 e 0! = 1.
Giacomo Tommei Calcolo combinatorio
Combinazioni semplici
EsercizioIn Coppa Davis il Capitano non giocatore di una Nazionale ha adisposizione quattro tennisti (A,B,C,D) e ne deve scegliere due percomporre la coppia per il doppio. In quanti modi puo scegliere?
SoluzioneRagioniamo in termini di disposizioni semplici: la prima persona puoessere scelta in 4 modi, mentre la seconda in 3; cosı facendo peroconsideriamo distinte, ad esempio, le coppie AB e BA, mentre ai finidel gioco non lo sono. Dobbiamo quindi dividere il numero delledisposizioni semplici ottenute (4 · 3 = 12) per il numero delle coppieequivalenti dato da 2! = 2. Il risultato e quindi
4 · 32
= 6
e ci fornisce il numero delle combinazioni semplici di 4 elementipresi a 2 a 2.
Giacomo Tommei Calcolo combinatorio
Combinazioni semplici
EsercizioIn Coppa Davis il Capitano non giocatore di una Nazionale ha adisposizione quattro tennisti (A,B,C,D) e ne deve scegliere due percomporre la coppia per il doppio. In quanti modi puo scegliere?
SoluzioneRagioniamo in termini di disposizioni semplici: la prima persona puoessere scelta in 4 modi, mentre la seconda in 3; cosı facendo peroconsideriamo distinte, ad esempio, le coppie AB e BA, mentre ai finidel gioco non lo sono. Dobbiamo quindi dividere il numero delledisposizioni semplici ottenute (4 · 3 = 12) per il numero delle coppieequivalenti dato da 2! = 2. Il risultato e quindi
4 · 32
= 6
e ci fornisce il numero delle combinazioni semplici di 4 elementipresi a 2 a 2.
Giacomo Tommei Calcolo combinatorio
Combinazioni semplici
Dato un insieme contenente n elementi distinti, si chiamacombinazione semplice degli n elementi, presi k a k, o di classe k(k ≤ n), un qualunque gruppo di k degli n elementi dell’insieme.
Il numero di combinazioni semplici di n elementi, presi k a k, e datoda
Cn,k =Dn,k
k!=
n (n− 1) (n− 2) . . . (n− k + 1)
k!=
(nk
)
Giacomo Tommei Calcolo combinatorio
Coefficiente binomiale
Proprieta (nk
)=
n!
k! (n− k)!
Dalla convenzione 0! = 1 si ha(n0
)= 1 e
(nn
)= 1
(nk
)=
(n
n− k
)Formula di Stifel(
nk
)+
(n
k + 1
)=
(n + 1k + 1
)Proprieta di ricorrenza(
nk + 1
)=
(nk
)n− k
k + 1
Giacomo Tommei Calcolo combinatorio
La formula del binomio di Newton
Esercizio Calcola lo sviluppo di (x + y)6.
SoluzioneE possibile rispondere rapidamente ed affermare che lo sviluppo di(x + y)6 e:
(x + y)6 = x6 + 6x5 y + 15x4 y2 + 20x3 y3 + 15x2 y4 + 6x y5 + y6
utilizzando il triangolo di Tartaglia (o di Pascal).
Giacomo Tommei Calcolo combinatorio
La formula del binomio di Newton
Esercizio Calcola lo sviluppo di (x + y)6.
SoluzioneE possibile rispondere rapidamente ed affermare che lo sviluppo di(x + y)6 e:
(x + y)6 = x6 + 6x5 y + 15x4 y2 + 20x3 y3 + 15x2 y4 + 6x y5 + y6
utilizzando il triangolo di Tartaglia (o di Pascal).
Giacomo Tommei Calcolo combinatorio
Il triangolo di Tartaglia
1
1 1
21 1
3 31 1
4 461 1
10 10 551 1
6 615 15 11 20
n=0
n=1
n=2
n=3
n=4
n=5
n=6
Triangolo di Tartaglia rappresentato fino a n = 6, naturalmente eestendibile a qualsiasi n ∈ N.
Giacomo Tommei Calcolo combinatorio
Il triangolo di Tartaglia
Come costruire il triangolo di Tartaglia
2
1 1
1 1
1
331 1
+
+ +
4 6 4 11
+ + +
Giacomo Tommei Calcolo combinatorio
Sviluppo di binomi
Qualunque siano i due numeri x e y e il numero naturale n si ha:
(x + y)n =
n∑k=0
(nk
)xn−k yk =
(n0
)xn +
(n1
)xn−1 y +
(n2
)xn−2 y2 + . . .
. . . +
(n
n− 2
)x2 yn−2 +
(n
n− 1
)x yn−1 +
(nn
)yn
Giacomo Tommei Calcolo combinatorio