Calcolo Combinatorio

[email protected]
a cura di Umberto Tenuta
Calcolo combinatorio
Una trattazione
elementare esposta in
modo essenziale e
funzionale.
N. Monforte
Liceo Scientifico Statale G.Sulpicio Veroli (FR)
A.S. 2000/2001
Note Bibliografiche
Diapositiva sommario






Disposizioni semplici
Disposizioni con Ripetizione
Permutazioni semplici
Permutazioni con oggetti identici
Combinazioni Semplici
Combinazioni con Ripetizione
Calcolo
combinatorio
Premessa Calcolo Combinatorio


Consideriamo un insieme di n oggetti:
G={a1,a2,a3,…an} con n0, di natura qualunque ma
perfettamente distinguibili l’uno dall’altro in base a
qualche caratteristica, ad esempio palline di diverso
colore; lettere dell’alfabeto; numeri diversi; ecc. .
Il “calcolo combinatorio” ha per scopo la costruzione
e la misurazione del n° di raggruppamenti che,
secondo un’assegnata definizione, si possono
formare con una prefissata quantità degli n oggetti
di G.
Calcolo
combinatorio
Disposizioni semplici
Osservazioni
Fissiamo un numero k0 che non superi n, si vogliono costruire tutti i possibili
raggruppamenti distinti che si ottengono prendendo k oggetti di Gn in modo che
valgano le seguenti proprietà:
 in ciascun raggruppamento figurano k oggetti senza ripetizioni;
 due qualsiasi raggruppamenti sono distinti se e solo se o uno di essi contiene
almeno un oggetto che non figura nell’altro oppure gli oggetti di un
raggruppamento sono gli stessi dell’altro raggruppamento ma è diverso l’ordine
con cui essi sono disposti.
I predetti raggruppamenti si dicono disposizioni semplici di n oggetti distinti di classe
k o presi a k a k. Tale numero si indica con il simbolo Dn,k e si dimostra che
n!
Dn,k=n(n-1)(n-2)...(n-k+1)= (n  k )!
Ad esempio si ha: D7,4=7654=840
D9,3=987=504
Osservazioni sulle Disposizioni Semplici
In generale Dn,k è uguale al prodotto di k numeri naturali, consecutivi, decrescenti a partire da n.
Consideriamo per fissare le idee, l’insieme G4={1,2,3,4},
 costruiamo le disposizioni semplici degli n=4 oggetti a k=1 a k=1; si hanno i
raggruppamenti seguenti:
1 2 3 4
e pertanto D4,1= 4
 costruiamo le disposizioni semplici degli n=4 oggetti a k=2 a k=2; si hanno i
raggruppamenti seguenti:
1 2
2 1
3 1
4 1 sicché resta verificato che D4,2 = 12.
1 3
2 3
3 2
4 2
1 4
2 4
3 4
4 3
 per costruire le disposizioni semplici degli n=4 oggetti a k=3 a k=3 occorre aggregare ai
precedenti raggruppamenti via via uno degli altri due oggetti che ancora non vi figurano:,
tenendo conto delle regole di composizione dei raggruppamenti per le disposizioni semplici
si ha:
1 2 3
2 1 3
3 1 2 D4,3=432=24
1 2 4
2 1 4
3 1 4 generalizzando si comprende la validità della formula
per il calcolo delle disposizioni semplici.
Calcolo
combinatorio
Disposizioni con Ripetizione
Osservazioni
Fissiamo un numero k0, senza alcuna limitazione superiore; si
vogliono costruire tutti i possibili raggruppamenti distinti,
prendendo k oggetti di Gn , in modo che valgano le seguenti
proprietà:
 in ciascun raggruppamento figurano k oggetti, potendovi uno
stesso oggetto figurare, ripetuto, sino ad un massimo di k
volte;
 due qualsiasi raggruppamenti sono distinti se e solo se o uno
di essi contiene almeno un oggetto che non figura nell’altro,
oppure gli oggetti sono diversamente ordinati oppure gli
oggetti che figurano in uno figurano anche nell’altro ma sono
ripetuti un numero diverso di volte.
I predetti raggruppamenti si dicono disposizioni con ripetizione degli
n oggetti di Gn, a k a k ( o di classe k).
Il n° delle predette disposizioni con ripetizione degli n oggetti di Gn,
a k a k si indica con D’n,k=nk
Osservazioni sulle Disposizioni con Ripetizione
Per fissare le idee consideriamo l’insieme G4={1,2,3,4}
 le disposizioni con ripetizione degli n=4 oggetti a k=1 a k=1
sono:
1
2
3
4 (1) ’
pertanto
D 4,1=4
 le disposizioni con ripetizione degli n=4 oggetti a k=2 a k=2 si
ottengono dalle (1) aggregando via via ciascuno degli oggetti
di G4, anche se già contenuti nel raggruppamento; esse sono:
1 1
2 1
3 1
4 1 Possiamo osservare che per ogni
1 2
2 2
3 2
4 2 disposizione con ripetizione di
1 3
2 3
3 3
4 3 classe uno se ne ottengono n=4 di
’
2
classe
2
e
pertanto
D
=4
=16
1 4
2 4
3 4
4 4
4,1
Calcolo
combinatorio
Applicazioni - 1
1. Quante parole anche prive di significato, si possono
costruire con 3 lettere dell’alfabeto, tutte diverse tra loro?
[disp. Semplici n=21, k=3 R.7980]
2. In quanti modi diversi 7 persone si possono sedere su 5
poltrone allineate di un cinema? [D(7,5)]
3. Quanti numeri di tre cifre, anche uguali tra loro, si possono
costruire con i primi cinque numeri naturali? [D’(5,3)]
4. Quante colonne d diverse si possono compilare nel gioco del
totocalcio? [D’(3,13)]
Calcolo
combinatorio
Permutazioni semplici
Le permutazioni semplici degli oggetti di Gn sono
le disposizioni semplici dei predetti n oggetti a
k=n a k=n. Si deduce che due qualsiasi
permutazioni semplici differiscono solo per
l’ordine con cui sono disposti gli n oggetti distinti
in esse contenuti.
Il loro n° è Dn,n ma si preferisce usare il simbolo
Pn
Evidentemente si ha: Pn=n(n-1)(n-2)(n3)…321=n! “enne fattoriale”.
Ad esempio, costruiamo e contiamo tutti gli
anagrammi, anche privi di significato, che si
possono formare con la parola “APE”.
APE PAE EAP AEP PEA EPA, sono sei, difatti
P3=3!=321=6
Calcolo
combinatorio
Permutazioni con oggetti identici
Ci proponiamo di anagrammare una parola contenente alcune lettere uguali; se
prendiamo in esame la parola “ALA”, notiamo che i suoi possibili anagrammi distinti
sono: ALA LAA AAL cioè soltanto tre e non sei come accade se le lettere sono tutte
diverse. In generale, volendo permutare n oggetti in cui ve ne siano  identici tra
loro, si ottiene un numero di permutazioni dato da:
( )
n
P
Pn n!
 
! !
Nell’esempio precedente avevamo n=3 ed =2 sicché gli anagrammi distinti
risultavano:
P
( 2)
3

3! 3  2  1

3
2! 2  1
Calcolo
combinatorio
Applicazioni - 2
Esempio: il numero di anagrammi distinti che si possono
costruire con la parola “MATEMATICA” è dato da:
P
( 3, 2 , 2 )
10

10!
 15120
3! 2! 2!
poiché il n° di lettere da permutare è
n=10 tra le quali la lettera “A” figura 3 volte, la lettera “M” 2
volte come la lettera “T”.
 Esercizio 1: Un negoziante deve eseguire 5 consegne di
merce acquistata da clienti abitanti ciascuno in 5 zone
diverse della città. determinare il n° di modi differenti di
eseguire le consegne. [R. 160]
 Esercizio 2: Quanti numeri naturali diversi di 6 cifre si
possono formare con le cifre del numero 775551. [R.
60]
Calcolo
combinatorio
Combinazioni Semplici
Osservazioni
Fissiamo un numero k0, che non superi n; si vogliono costruire tutti i possibili
raggruppamenti distinti che si ottengono prendendo k oggetti di G n in modo che valgano le
seguenti proprietà:
 in ciascun raggruppamento figurano k oggetti senza ripetizioni;
 due raggruppamenti sono distinti se e solo se uno di essi contiene almeno un
oggetto che non figura nell’altro.
Segue, pertanto, che due raggruppamenti che differiscono solo per l’ordine con cui in essi
sono disposti gli oggetti sono da ritenersi identici.
I predetti raggruppamenti si dicono “Combinazioni semplici” degli n oggetti di G n di classe
k od a k a k.
Il numero delle predette combinazioni semplici di n oggetti distinti di classe k si indica con
il simbolo di Cn,k
Si dimostra che :
C
n,k

D
n,k
k!
Questa formula è giustificata dal fatto che da ogni
combinazione semplice si possono ottenere, permutando in tutti i modi possibili i k oggetti
che la compongono, k! disposizioni semplici.
Osservazioni sulle Combinazioni Semplici 1/3
Consideriamo ad esempio l’insieme G4={1,2,3,4,5}
 le combinazioni semplici degli n=4 oggetti di classe k=1 sono:
1234
 le combinazioni semplici degli n=4 oggetti di classe k=2 si ottengono
dalle precedenti aggregaziondo, via via, solo quegli elementi che, in
G4 seguono l’oggetto già presente nel raggruppamento, ossia:
1 2
2 3
3 4
1 3
2 4
1 4
 le combinazioni semplici degli n=4 oggetti di classe k=3 si ottengono
da quelle di classe 2 aggregando, via via, solo quegli elementi che in
G4, seguono l’oggetto che figura più a destra del raggruppamento,
ossia:
1 2 3
2 3 4
1 2 4
1 3 4
Osservazioni sulle Combinazioni Semplici 2/3
Nota: il numero Cn,k si india anche con  kn  che si
 
legge “n su k”, denominato “coefficiente
binomiale” di ordine n e di classe k.
E’ abbastanza facile, posto per definizione  n0   1 ,
 
dimostrare la validità delle seguenti formule:
C
n,k

n!
k! (n  k )!
;
 n   n   n  1  n   n 
  
   
   
 ; 
k

1
k

1
 
 k 
k  n  k  
Può essere utile ricordare la “formula del binomio
di Newton”:
n
(a  b)      a n  k  b k
k 0  k 
n
n
Osservazioni sulle Combinazioni Semplici 3/3
Sussistono le seguenti proprietà:
n
1.    1
0
n
2.    1
n
n
3.    n
1
 n 
  n
4. 
 n 1
n  n 

5.    
k  n  k 
 n  n  (n  1)  (n  k  1)
,k  0
6.   
k
k
!
 
 n  1  n   n 
  
    , n  , k  1,, n
7. 
n
k

1

 
 k 
Calcolo
combinatorio
Combinazioni con Ripetizione
Fissiamo un numero k0, senza alcuna limitazione superiore; si vogliono costruire
tutti i possibili raggruppamenti distinti, prendendo k oggetti di Gn, in modo che
valgano le seguenti proprietà:
 in ciascun raggruppamento figurano k oggetti di Gn, potendovi uno stesso
elemento figurare ripetuto fino ad un massimo di k volte;
 due raggruppamenti sono distinti se e solo se o uno di essi contiene almeno un
oggetto che non figura nell’altro oppure gli oggetti che figurano in uno
figurano anche nell’altro ma sono ripetuti un numero diverso di volte.
I predetti raggruppamenti si dicono “combinazioni con ripetizione degli n oggetti
di Gn, a k a k” o di classe k.
 n  k  1


Il loro numero si indica con il simbolo C’n,k. Si dimostra che: C n,k   k 


'
Calcolo
combinatorio
Applicazioni - 3
Esercizio 1: Un barman dispone di 30 liquori diversi.
Quanti coktails diversi potrà preparare utilizzando, ogni
volta, 3 dei predetti liquori? [R. 4060]
Esercizio 2: Quanti terni si possono fare con i 90 numeri del
gioco del lotto? [R. 117480]
Esercizio 3:Quante sono le diagonali di un poligono
convesso di n lati?
[R. le diagonali di un poligono sono i segmenti che
uniscono due vertici non consecutivi. Il numero totale dei
segmenti definiti dagli n vertici del poligono è: C  n  (n2! 1) ,
n,2
ma in questo numero è compreso anche il numero dei lati,
pertanto va sottratto n.
Esercizio 4: In un campionato di pallavolo le squadre che si
devono incontrare in 10 campi sono 15. Quanto dura il
campionato? [R. 21 giorni]
Note Bibliografiche
“Calcolo Combinatorio e delle probabilità”
M. Battelli – U. Moretti
C.P.E. Oggiscuola – Modena
Lineamenti di Matematica
Probabilità e statistica.
N. Dodero – P. Baroncini – R. Manfredi
G.& C. Ghisetti e Corvi Editori
ISBN 88-8013-621-6
Atlante di Matematica
F.Reinhardt – H. Soeder
Hoepli – Milano
ISBN 88-203-2050-9