Calcolo combinatorio
Una trattazione elementare
Definizione
Oggetto del calcolo combinatorio è quello di determinare il numero
dei modi mediante i quali possono essere raggruppati, secondo
prefissate regole, gli elementi di uno stesso insieme o di più insiemi.
Il problema, all’apparenza, sembra banale: ciò è vero se il numero
degli elementi presi in considerazione è piccolo, ma quando questo
numero è elevato si presentano delle difficoltà nel formare tutti i
raggruppamenti possibili, con e senza considerare ripetizioni.
Ci si può, per esempio, chiedere:
Esempi



In quanti modi diversi si possono scegliere tre libri
da una libreria che ne contiene 12?
Quante parole di 5 lettere posso formare con un
alfabeto formato da 21?
Nel menù di un ristorante si può scegliere tra cinque
primi piatti, sei secondi e sette dessert: quanti tipi
di pasti, con almeno una portata diversa, può
somministrare il ristoratore?
Diapositiva sommario






Disposizioni semplici
Disposizioni con Ripetizione
Permutazioni semplici
Permutazioni con oggetti identici
Combinazioni Semplici
Combinazioni con Ripetizione
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 numero di raggruppamenti che,
secondo un’assegnata definizione, si possono
formare con una prefissata quantità degli n oggetti
di G.
Disposizioni semplici
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
Dn,k=n(n-1)(n-2)...(n-k+1)=
n!
(n  k )!
Ad esempio si ha: D7,4=7654=840
D9,3=987=504
Disposizioni semplici
n!
Dn,k= (n  k )!
Dn,k =n(n-1)(n-2)...(n-k+1)
Disposizioni semplici
Quante parole di 5 lettere posso formare con un
alfabeto formato da 21 (senza ripetere mai la
stessa lettera in ogni parola)?
- Se cambia una lettera cambia la parola
- Ordine diverso delle lettere -> parola diversa!
21!
D21,5 = (21  5)!
D21,5 = 21*20*19*18*17*…….*6 = 2.441.880
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

1
1
1
e pertanto D4,1= 4 e cioè (4*3*2*1)/(3*2*1)
costruiamo le disposizioni semplici degli n=4 oggetti a k=2 a k=2; si hanno i raggruppamenti
seguenti:
2
2 1
3 1
4 1 sicché resta verificato che D4,2 = 12.
3
2 3
3 2
4 2
4
2 4
3 4
4 3
OVVIAMENTE PRESUPPONIAMO che (1,2) e (2,1) siano risultati diversi!!!

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.
Disposizioni con Ripetizione
Fissiamo un numero k0; 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
Disposizioni con ripetizione
1
k
D n,k=n
1
D
n,k
=n*n*n*n*…..*n
k volte
Disposizioni con ripetizione
Quante parole di 5 lettere posso formare con un
alfabeto formato da 21 (ripetendo anche più volte
la stessa lettera in ogni parola)?
- Se cambia una lettera cambia la parola
- Ordine diverso delle lettere -> parola diversa!
- Stesse lettere ma con numero di ripetizioni
diverse (es. aaabb e aabbb sono diverse)
D21,5 = 215
D21,5 =21*21*21*21*21=4084101
ovviamente sono più del caso senza ripetizioni!
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.
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
1 4
2 4
3 4
4 4 classe 2 e pertanto D 4,1=4 =16
Esercizi
1. In quanti modi diversi 7 persone si possono sedere su 5
poltrone allineate di un cinema? con o senza ripetizioni???
[D(7,5)]
2. Quanti numeri di tre cifre, anche uguali tra loro, si possono
costruire con i primi cinque numeri naturali? con o senza
ripetizioni??? [D’(5,3)]
3. Quante colonne d diverse si possono compilare nel gioco del
totocalcio? con o senza ripetizioni??? [D’(3,13)]
4. Se volessi giocare un sistema tenendo 4 fisse e 9 doppie,
quante colonne verrebbero fuori?
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 numero è Pn = n(n-1)(n-2)(n-3)…321=n! “n
fattoriale”.
RICORDA CHE TUTTI GLI ELEMENTI SONO
DIVERSI TRA LORO!
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*2*1=6
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  32!!  32 211  3
( 2)
3
Esercizi
Esempio: il numero di anagrammi distinti che si possono costruire
con la parola “MATEMATICA” è dato da: P10
( 3, 2 , 2 )

10!
 15120 poiché
3! 2! 2!
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 numero di ordini differenti per
effettuare le consegne. [R. 160]
 Esercizio 2: Quanti numeri naturali diversi di 6 cifre si
possono formare con le cifre del numero 775551. [R. 60]
Combinazioni Semplici
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 raggruppamenti sono distinti se e solo se uno di essi contiene
almeno un oggetto che non figura nell’altro.
Segue, pertanto, che se due raggruppamenti differiscono solo per
l’ordine con cui sono disposti in essi gli oggetti, allora li
consideriamo identici!!
I predetti raggruppamenti si dicono “Combinazioni semplici” degli n
oggetti di Gn 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
D

n,k
n,k
k!
=
n!
(n  k )! k!
RIFLETTI: 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}
 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 C  Dk! si indica 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 ,
n,k
n,k
 
dimostrare la validità delle seguenti formule:
C
n,k

n!
k! (n  k )!
;
 n   n   n  1  n   n 
   
 ; 
  
   
k
n

k
k

1
k

1
  
 
 
 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 
Combinazioni con Ripetizione
Fissiamo un numero k0; 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.
Il loro numero si indica con il simbolo C’n,k. Si dimostra che:
C
'
n ,k
 n  k  1
 cioè
 
 k 
C n,k 
D
n  k 1, k
k!
Esercizi
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?
- Se cambi l’ordine cambia il terno? (non è una disposizione
ma una combinazione)
- In un terno possono esserci due numeri uguali? (è quindi una
combinazione senza ripetizione)
[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!)!*2!  n  (n2! 1) , ma in
n,2
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. (un campionato è fatto
da andata e ritorno, quale tipo di combinazioni utilizziamo?)
Quanto dura il campionato? [R. 21 giorni]
RICAPITOLAZIONE!
DISPOSIZIONI SEMPLICI
1) Senza ripetizioni;
2) Ordine diverso = raggruppamento diverso
Dn,k=
DISPOSIZIONI CON RIPETIZIONI
1) Con ripetizioni (sono presenti più volte gli stessi
elementi)
2) Ordine diverso = raggruppamento diverso
D1n,k=nk
PERMUTAZIONI SEMPLICI
1) Numero max di elementi (n)
2) differiscono solo per l’ordine: ordine diverso =
raggruppamento diverso
3) TUTTI GLI ELEMENTI SONO DIVERSI TRA LORO
Pn = n!
PERMUTAZIONI CON ELEMENTI COINCIDENTI
1) Con ripetizioni (sono presenti più volte gli stessi
elementi)
2) Ordine diverso = raggruppamento diverso
In generale, volendo permutare n oggetti in cui ve ne siano  identici tra loro, si
( )
n
P
ottiene un numero di permutazioni dato da:
Pn n!


! !
RICAPITOLAZIONE!
COMBINAZIONI SEMPLICI
1) Senza ripetizioni;
2) Ordine diverso = stesso raggruppamento
n!
D
Dn,k= C  k! = (n  k )!k!
n,k
n,k
COMBINAZIONI CON RIPETIZIONI
1) Con ripetizioni (sono presenti più volte gli stessi
elementi)
2) Ordine diverso = raggruppamento diverso
C
'
n ,k
 n  k  1
 cioè
 
 k 
C n,k 
D
n  k 1, k
k!