CALCOLO COMBINATORIO
Prof Sandro Pistori
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Qualche problema introduttivo
1.
In quanti modi diversi 3 ragazzi di una compagnia di 5 amici si
possono sedere su 3 poltrone libere di un cinema?
2.
Quanti numeri di 4 cifre si possono comporre con le cifre
1,2,3,4,5,6?
3.
Quanti anagrammi si possono comporre con le lettere della parola
ROMA?
E con la parola ALA?
4.
Quanti terni si possono fare con i 90 numeri del Lotto?
5.
In quanti modi diversi 7 caramelle identiche possono essere
distribuite tra 4 bambini?
E se le caramelle fossero diverse?
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Il calcolo combinatorio
il Calcolo combinatorio fornisce quegli
strumenti di calcolo per determinare il numero di raggruppamenti che si
possono formare con un numero k di oggetti presi da un insieme contenente
n oggetti ( n  k ) secondo le modalità seguenti:
se k = n otterremo dei gruppi ordinati permutazioni.
k oggetti possono formare gruppi ordinati: disposizioni;
k oggetti possono formare gruppi non ordinati: combinazioni;
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Problema 1
Raggruppare gli elementi a,b,c a gruppi di 2
con elementi che non possono ripetersi
1° modo
COPPIE ORDINATE:
ab
ac
ba
bc
ca
cb
2° modo
COPPIE PER LE QUALI NON IMPORTA
L’ORDINE:
ab
ac
bc
DISPOSIZIONI semplici (D3,2)
STAGE OLIMPICO 2009-2010
COMBINAZIONI semplici (C3,2)
CALCOLO COMBIANTORIO
Problema 2
Raggruppare gli elementi a, b, c a gruppi di 2
con elementi che possono ripetersi
1° modo
COPPIE ORDINATE:
aa ab
ac
bb ba
bc
cc ca
cb
2° modo
COPPIE PER LE QUALI NON IMPORTA
L’ORDINE:
aa
ab
ac
bb
bc
cc
DISPOSIZIONI con ripetizione
(D’3,2)
STAGE OLIMPICO 2009-2010
COMBINAZIONI con ripetizione (C’3,2)
CALCOLO COMBIANTORIO
Quindi…
I RAGGRUPPAMENTI POSSONO ESSERE:
SEMPLICI:
CON RIPETIZIONE:
quando gli oggetti sono tutti diversi
quando gli oggetti vi figurano una o più volte
E riassumendo:
Permutazioni semplici o con ripetizione
Disposizioni semplici o con ripetizione
Combinazioni semplici o con ripetizione
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Fattoriale
Il FATTORIALE di un numero intero positivo n è il prodotto di tutti gli
interi positivi minori o uguali ad n
In simboli:
n! = n(n -1)(n -2)(n -3)…1
Si può quindi scrivere in modo ricorsivo
n! = n(n -1)!
Da cui nasce l’esigenza di definire 0!=1 infatti
1!=1(1-1)!=1 0!=1
Esempi:
5!=5 4 3 2 1 = 120
6!=6 5!= 6 120=720
10!=3.628.800
17!=35.568.7428.100.000
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Gli anagrammi (PERMUTAZIONI)
Quanti sono gli anagrammi anche privi di senso della parola MARE?
4
3
2
1
4  3  2 1  4!  24
P(n)  n(n  1)( n  2)... 1  n!
Corrisponde ai modi diversi di ordinare tutte e quattro le lettere che
in questo caso sono diverse: permutazione semplice di n oggetti
Quanti sono gli anagrammi della parola MAMMA?
Ad esempio
MAMAM MAMAM MAMAM
rappresentano sempre la stessa “parola”
MAMAM
Faccio finta che siano tutti diversi e poi li divido per tutti i possibili
scambi che mi producono la stessa parola
5!
5  4  3!

 10
3!2!
3!2
STAGE OLIMPICO 2009-2010
P ' (n ) 
n!
 ! !...
CALCOLO COMBIANTORIO
DISPOSIZIONI
Le disposizioni semplici di k oggetti presi da un gruppo di n oggetti sono
Dn,k= n(n-1)…(n-(k-1))= n(n-1)…(n-k+1)=
n(n-1)…(n.-k+1)(n-k)(n-k-1)…1/(n-k)!
Dn,k = n!/(n-k)!
Le disposizioni con ripetizione di k oggetti presi da un gruppo di n oggetti sono
D’n,k=n k
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Esempi
Quanti sono numeri di 4 cifre tutte distinte e non nulle nel sistema decimale?
9 8 7 6
Disposizione semplice D9,4 = 9!/(9-4)! = 9!/5!=3024
Quante sono le combinazioni possibile per un lucchetto a 5 cifre?
Quanti sono i sottoinsiemi di un insieme con n elementi?
A B
0 0
1 0
1 1
…
C
1
0
1
D
0
0
1
E
1
0
1
F
1
0
1
G
0
0
1
H
1
0
1
STAGE OLIMPICO 2009-2010
= 2 n = D’2,n
CALCOLO COMBIANTORIO
COMBINAZIONI
Combinazioni semplici
Facciamo finta che sia una disposizione e poi dividiamo per il numero di
scambi che danno origine allo stesso gruppo di k oggetti
ABCDEF:
ABCD ACBD ADBC… sono le permutazioni di 4 elementi
Cn,k=Dn,k/ k! =
n
n!
  
k ! (n  k )!  k 
COEFFICIENTE
BINOMIALE
Combinazioni con ripetizione
C
'
n ,k
 n  k  1

 
k


STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Esercizi
In quanti modi diversi si possono sedere 4 amici in un scompartimento da
sei posti di un treno?
In quanti modi diversi possono venire occupati 6 posti di uno
scompartimento di un treno da quattro persone?
Quante sono le diagonali di un poligono di n lati?
Quanti sono i punti che vengono individuati da 20 rette complanari a due
a due non parallele?
Quanti sono i punti di intersezione che vengono individuati da 20 rette se
7 di esse sono parallele e le restanti no?
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Il binomio di Newton
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Ancora sui coefficienti binomiali
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO
Un problema già visto…
Quanti sono i sottoinsiemi di un insieme A di n elementi?
Siano
k0 tutti gli insiemi con nessun elemento
k1 numero degli insiemi con un elemento
k2 numero degli insiemi con due elementi
…
kn numero degli insiemi con n elementi
n n
n n n
n
Allora | P(A) | = k0+k1+k2+…+kn=1        ... 1           ...    
1   2 
 0  1   2 
n
 (1  1) n  2 n
STAGE OLIMPICO 2009-2010
CALCOLO COMBIANTORIO