Parte 1
"calcolo combinatorio"
1
Parte 1
"calcolo combinatorio"
si intende una branca della Matematica che studia i modi
di raggruppare ed ordinare k oggetti presi da un
insieme assegnato di n oggetti, con l'obiettivo finale di
contare il numero dei possibili raggruppamenti od
ordinamenti
 Gli oggetti possono essere ripetuti oppure comparire
una sola volta
 L’ordine può essere importante oppure no
 K può essere > < = n
I raggruppamenti sono di sei tipi: tre semplici e
tre con ripetizione
2
Parte 1
 I diversi modi di “mischiare” n elementi in k
posti (con e senza ripetizione)sono:
 Permutazioni : n=k es: gli anagrammi
 Disposizioni: l’ordine è importante! es: la
pass word, la cassaforte …
 Combinazioni: l’ordine non conta, è indifferente
es: il terno al lotto, il concorso …
3
Parte 1
 Una sequenza di n elementi si dice, genericamente,
n-upla
 (per n=2 si parlerà di "coppia", per n=3 di "terna", per n=4
di "quaterna",
 per n=5 di "cinquina", per n=6 di "sestina", per n>6 di
"sequenza di 6, 7, 8, ... elementi").
 Quando in un'n-upla consideriamo "importante"
l'ordine in cui gli elementi si susseguono, parleremo di
n-upla "ordinata", e la indicheremo con parentesi
tonde: (x1, x2, …., xn)
 NB (a,e,i) è diverso da (e,i,a)
 Quando consideriamo irrilevante l’ordine, parleremo di
n-upla "non ordinata" e useremo le graffe:
 { x1, x2, …., xn }
4
Parte 1
N!
 n! = 1.2.3. … (n-2).(n-1).n
 oppure, in modo compatto
 Es. 7!=1. 2.3.4.5.6.7=5040
n
n! =
j
j 1
 Per convenzione 0!=1 1!=1
( definizione “ricorsiva”)
 n!=n.(n-1)!
 n!
 n.n  1n  2 .....(k  1) 12!  12.11.10.9.8.7.6.5.4.3.2.1
k!
5!
5.4.3.2.1
n!
 n.n  1n  2.....(n  (k  1))

(n  k )!
12!
12.11.10.9.8.7.6.5.4.3.2.1

(12  5)!
7.6.5.4.3.2.1
5
Parte 1
n!




Simbolo inventato nel 1808 da Christian Kramp (Germania) a significare lo stupore con
cui cresce rapidamente
In inglese è anche detto n-bang o, dagli studenti, n-shriek + urlo di terrore.
Nel 1950 Horace Uhler calcolò 450! senza calcolatori elettronici e lo chiamò “ il fattoriale
delle Mille e una Notte perché ha 1001 cifre
450! =
173336873311263265934471314610457939967781126520905101556920750955533300168343675
060467508829043871061458112845184240978586185838063016502083472961813516675701719
187004222809622372722306635280840380623123693426741350366101015088382204949709297
390116367937661650237308538964039015908361441495944326842045137847164023031826040
946839933150613025639183853033415106067614624202058200069363520959674171831915387
256175095213805567813091954298002292738033425535581645919962989123685985477711791
584613513400689056471276581648363771263037749233600780723074620085543550683614481
266062811457609604991878134283979248405925045378494874250604884810365714479570467
886357429367146151762191484697431029799497407144851047161696640523973926028484086
940074089989011274929051715144734313866333924920406615226923030438139605419660932
242438092251372688517179043032140582384479361116785682369730362384046265078906880
000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000
6
Permutazioni
Parte 1
Dati n oggetti, essi si possono "mettere in fila"
(o “mettere in coda”, o “mettere in colonna”)
in n! modi diversi
1.ANAGRAMMI ( Permutazioni semplici )
Grafico ad albero rovesciato
AMO
AMO AOM MAO MOA OMA OAM
M
A
O
M
AMO
P3= 3! = 3*2*1=6
AOM
A
MAO
O
O
MOA
M
OMA
A
OAM
Pn= n!= n*(n-1)*(n-2)…..3*2*1
7
Parte 1
 Dati n oggetti, essi si possono "mettere in fila"
(o “mettere in coda”, o “mettere in colonna”)
in n! modi diversi
 Infatti, per la scelta del primo oggetto della fila abbiamo n
possibilità;
 a ciascuna di queste n possibilità sono abbinate (n-1)
possibilità di scelta per il secondo oggetto della fila;
 ad ognuna delle n·(n-1) possibilità per i primi due oggetti
corrispondono (n- 2) possibilità di scelta per il terzo
oggetto della fila; ... ;
 in totale, quindi, n oggetti possono essere ordinati
(=messi in fila, o in coda, o in colonna) in
 n·(n-1)·(n-2)· … ·3·2·1 = n! modi diversi.
8
Parte 1
AMA CA
AM A C A
AM AC A
MA C A A
5!
3!
5!/3!
9
2.ANAGRAMMI CON LETTERE UGUALI
Pn(α ,β ,γ ) =
( Permutazioni con ripetizioni )
Parte 1
n!
α! β! γ!
AMA AAM MAA MAA AMA AAM
M
A
A
M
AMA
AAM
A
MAA
Anagrammiamo “ANAGRAMMIAMO”:
A si ripete 4 volte M si ripete 3 volte
A
A
MAA
M
3! 3 • 2!
=
=3
2!
2!
A
AMA
n=12 α= 4
P12(4,3) =
P3(2) =
AAM
β=3
12! 12 • 11• 10 • • • 4 • 3 • 2 • 1
=
= 220
4!3!
3! 4 • 3 • 2 • 1
Calcoliamo: quanti numeri possiamo generare con le cifre 3,5,8 ?
Ragiono…è come anagrammare…..3 oggetti in tre posti…allora la risposta
viene dalle permutazioni semplici…..P3=3!=6….358;385;835;853;538;583
10
Parte 1
Il coefficiente BINOMIALE
 si legge “coefficiente
binomiale n su k” e si
ha dunque
Esempi
7
7!
7!
7.6.5.4.3.2.1
  


. 4.3.2.1
 3  3!(7  3)! 3!4! 3.2.1
16  16! 16.15.14.13.12.11.10! 16.15.14.13.12.11.10!
  



6.5.4.3.2.1.10!
6.5.4.3.2.1.10!
 6  6!10!
 7.8.13.11  8008
11
Parte 1
Il coefficiente BINOMIALE
 Proprietà:
2005 sess.ordinaria maturità di
ordinamento…
Ma anche 1981 … e 2001
12
Parte 1
Il binomio di Newton
 Si chiama "binomio di Newton" la formula per lo
sviluppo dell'n-esima potenza di un binomio. Tale
formula è:
=
4 4 0 4 3 1 4 2 2 4 1 3 4 0 4
a  b    a b   a b   a b   a b   a b
0
1
2
3
4
4
a  b 
4
 1 a 4b 0  4 a 3b1  6 a 2b 2  4 a1b 3  1 a 0b 4
13
Parte 1
Triangolo di tartaglia
0
1
1
1
2
1
3
1
5
1
6
1
7
1
8
1
9
10
2
1
4
1
1
9
10
45
84
120
10
35
56
5
35
126
1
6
21
56
126
252
1
15
70
210
1
4
20
21
36
3
10
15
28
1
6
5
7
8
3
4
6
1
7
28
84
210
1
1
8
36
120
1
9
45
1
10
1
Proviamo a verificare qualche valore
 5  5! 5.4.3.2.1
  

 10
 2  2!3! 2.1.3.2.1
 8  8! 8.7.6.5.4.3.2.1
  

 56
 5  5!3! 5.4.3.2.1.3.2.1
14
Parte 1
Dimostrazione della formula






(a+b)n = (a+b)(a+b) .... (a+b) dove a secondo membro abbiamo n
fattori.
Si può pensare di effettuare la moltiplicazione scegliendo, da
ciascun fattore (a+b), il termine a, oppure il termine b, in tutti i modi
possibili, per poi sommare algebricamente i prodotti così ottenuti.
Es se ho (a+b)7= (a+b) (a+b) (a+b) (a+b) (a+b) (a+b) (a+b)
posso prendere 5 a e 2 b a caso :
a.a.a.b.b.a.a. oppure a.a.a.a.a.b.b oppure a.b.a.a.b.a.a = a5b2
Ora, se io scelgo, ad esempio, k volte il fattore a e n-k volte il fattore
b, avrò il monomio akbn-k
Quante volte comparirà, questo monomio, nella somma finale?
Tante volte quanti sono gli anagrammi con a ripetuto k volte e b
ripetuto n-k volte
E tali modi sono ...
n
n!
  
k!(n  k )!  k 
15
Es “cattivello”…
Parte 1
… ma che si è visto proprio alla maturità
del 2000 e del 2001
Dimostrare che:
Dim:
Dividendo il primo e l'ultimo termine dell'uguaglianza per an abbiamo che:
Oppure provare con 2n=(1+1)n cioè con a=1 e b=1…..
16
Parte 1
disposizioni
 Se una prima scelta può essere fatta in r modi diversi, per
ciascuno dei quali una seconda scelta può essere effettuata
in s modi diversi, e, per ciascuno dei modi in cui si sono
compiute le prime due scelte, una terza scelta può essere
effettuata in t modi diversi ecc., allora la successione di
tutte le scelte può essere compiuta in r·s·t ... modi diversi
17
Parte 1
3. CONCORSI (Disposizioni semplici)
n!
D n,k = n • (n - 1) • (n - 2)....(n - (k  1)) 
(n - k)!
Ad un concorso si iscrivono 4 persone per 2 posti disponibili, quante sono gli esiti
possibili tenendo conto dell’ordine di arrivo?
Ragiono: al primo posto ci potrebbero finire le quattro persone a b c d, ma al secondo
posto ci possono finire solo tre persone per ogni persona che è finita al primo posto
b
ab
c
ac
c
b
a
d
a
ad
ba
4
c
3
a
d
bc
d
bd
ca
b
cb
d
a
cd
da
b
c
db
dc
D4,2 = 4 • 3 = 12
18
Drn,k = nk
4. CASSAFORTE (Disposizioni con ripetizione)
Parte 1
Quante possibilità ci sono di formare una “combinazione” segreta di 4 cifre ?
0
3
3
5
3
1
1
9
Queste sono due disposizioni accettabili. Ragioniamo: nella prima cella posso
mettere 10 cifre diverse; ma anche nella seconda cella posso mettere 10 cifre
diverse. Allora per ogni cifra della prima cella posso associare una delle possibili
10 cifre della seconda, e via così.
10 10 10 10
10*10*10*10=104
In generale le disposizioni di n oggetti da sistemare con ripetizione in k posti è nk
(in questo caso k può superare n, vedi totocalcio).
esempio: quante parole di quattro lettere posso comporre con 26 lettere a
disposizione?
26*26*26*26=264 = 456.976
esempio: quante colonne di totocalcio sono possibili?
4.782.969
3*3….3*3*3 = 314 =
19
Parte 1
combinazioni
 Quando si gioca al lotto cinque numeri, non è
richiesto di indovinare anche l’ordine con il
quale questi numeri vengono estratti.
 In questo caso se giocassi la cinquina
8;17;56:12;81 vincerebbe tanto quanto
56;12;8;17;81 oppure
81;56;17;12;8
 Queste tre cinquine sono praticamente la stessa
cinquina anche se permuto i cinque numeri fra
loro.
20
Parte 1
5. GIOCO DEL LOTTO (Combinazioni)
E come faccio a contare quante sono?
Si tratta di considerare tutte le disposizioni possibili di 90 numeri in 5 posti senza considerare
l’ordine. Ossia ogni disposizione va divisa per il numero di permutazioni di 5 oggetti. Allora
quante cinquine sono possibili al gioco del lotto?
D
C90,5 =
C n,k
90,5
5!
=
90 • 89 • 88 • 87 • 86
= 43.949.268
5 • 4 • 3 • 2 •1
n!
D
n
n • (n - 1) • (n - 2)....(n - k  1) (n  k )!
n!
= n,k 


  
k!
k!
k!
(n  k )! k!  k 
Se nel concorso di 4 persone per due posti di lavoro, non tenessi conto del piazzamento ma solo dei
vincitori, allora ab=ba come ac=ca ecc. si avrebbe allora :
C4,2 =
b
ab
c
ac
d
ad
c
b
a
a
ba
c
bc
d
bd
D4,2 4 • 3
=
= 6 = (24 )
2!
2 •1
d
a
ca
b
cb
d
cd
a
da
b
db
c
21
dc
6. I SEGMENTI (Combinazioni con ripetizione)
Crn,k = Cn+k -1,k =
n • (n + 1) • (n + 2)....(n + k - 1)
k!
Parte 1
Ci si chiede quante combinazioni di n oggetti, anche ripetuti, si possono mettere in
k posti (in questo caso k può superare n).
Supponiamo di dover calcolare quanti segmenti posso costruire con 3 punti
allineati, comprendendo anche il punto come segmento nullo Proviamo a fare un
grafico ad albero. (Si ricorda che una combinazione considera ab=ba, ac=ca, ecc.)
A
B
C
Primo estremo
Secondo estremo
a
a
aa
Proviamo a contare:
b
ab
n = 3; k = 2;
b
c
c
b
c
ac
bb
bc
C r3,2 = C 4,2 =
c
cc
3•4
=6
2!
Supponiamo di voler intervistare un campione di due individui su una popolazione di 3;
l’intervista può anche essere fatta due volte sullo stessa persona ma non interessa in
che ordine viene fatta. Quanti sono i possibili campioni ? C r = C = 3 • 4 = 6
3,2
4,2
2!
22
Parte 1
La grande illusione….
23
Parte 1
Qual è la probabilità di azzeccare l' "estratto semplice"?
Io gioco un numero, ad esempio il 44, e "spero che esca".
I casi possibili sono le cinquine non ordinate costruibili coi 90 numeri 1, 2, ... 90, cioè
e i casi favorevoli sono tanti quante le cinquine che contengono il 44.
Ma queste sono tante quante le quaterne costruibili utilizzando gli 89 numeri rimanenti, cioè
La probabilità richiesta è pertanto
Qual è la probabilità di azzeccare l' "ambo" ?
Io gioco 2 numeri, ad esempio il 44 e il 55, e "spero che escano".
I casi possibili sono le cinquine non ordinate costruibili coi 90 numeri 1, 2, ... 90, cioè
e i casi favorevoli sono tanti quante le cinquine che contengono il 44 e il 55.
Esse sono tante quante le terne costruibili utilizzando gli 88 numeri rimanenti, cioè
La probabilità richiesta è pertanto
24
Parte 1
Qual è la probabilità di azzeccare il "terno" ?
Io gioco 3 numeri, ad esempio il 44, il 55 e il 66, e "spero che escano".
I casi possibili sono le cinquine non ordinate costruibili coi 90 numeri 1, 2, ... 90, cioè
e i casi favorevoli sono tanti quante le cinquine che contengono il 44, il 55 e il 66.
Esse sono tante quante le coppie costruibili utilizzando gli 87 numeri rimanenti, cioè
La probabilità richiesta è pertanto
Qual è la probabilità di azzeccare la "quaterna"?
Qual è la probabilità di azzeccare la "cinquina"?
25
Parte 1
Lotto = gioco iniquo!
Notare come il lotto sia un gioco "iniquo": a fronte delle probabilità sopra calcolate,
lo Stato restituisce soltanto:
ho una probabilità di
vincere di
Ma, in caso di vincita, mi
viene pagata soltanto
una cifra uguale alla
posta giocata
moltiplicata per
Estratto semplice
1/18
11,232
Ambo
2/801 (circa 1/400)
250
Terno
1/11.748
4250
Quaterna
1/511.038
80.000
Cinquina
1/43.949.268
1.000.000
Quando gioco la
combinazione:
Ha senso giocare solo se si giocano
piccole somme di denaro su combinazioni difficili,
con la quasi certezza di perdere ma con la remota speranza di
vincere grosse cifre.
26
Parte 1
L’emozione di un sogno
milionario giustifica una
piccola cifra giocata,
ma quasi certamente persa.
Lo “sfizio” di avere in tasca 1 possibilità su 622 milioni di
aggiudicarsi il jeck-pot miliardario del super-enalotto può
valere forse i pochi euro della giocata. Ma chi gioca
centinaia di euro incrementa soltanto le entrate di quella
che è stata chiamata …
La tassa sugli
illusi !!!
27