1
Calcolo Combinatorio (richiami) 1/13
Def. Principio di moltiplicazione
Se una procedura P1 può essere eseguita in n1 modi diversi, dopo questa una seconda procedura
P2 può essere eseguita in n2 modi diversi, dopo questa una terza procedura P3 può essere eseguita
in n3 modi diversi e così via … Allora la procedura P che consiste nella successione delle procedure
P1,P2,P3,… nell’ordine, può essere eseguita in n modi diversi con:
....321 nnnn
Il calcolo combinatorio (Analisi combinatoria) si prefigge di stabilire quanti gruppi si possono
formare da un certo numero di oggetti, una volta nota la legge di formazione dei gruppi stessi.
Es. Lancio di due dadi
3
Disposizioni semplici 2/13
Si considerino n oggetti, che indichiamo con:
, ..... , , 21 naaa
Sia k un intero positivo con k≤n, si vogliono formare dei gruppi di k oggetti prendendoli
dall’insieme degli n oggetti precedenti in modo tale che due gruppi differiscano o per natura degli
elementi o per l’ordine in cui compaiono.
Def. Disposizione semplice(*)
Si chiama disposizione semplice di n oggetti di classe k (oppure a k a k) (k≤n) il
numero dei possibili gruppi che si possono formare prendendo k oggetti dagli n oggetti
dati e considerando i gruppi diversi per natura o per ordine. Indicheremo tale numero
con knD ,
(*) Nota: «semplice» qui serve ad indicare senza ripetizione (vedi poi)
4
Disposizioni semplici 3/13
Disposizione di 4
oggetti di classe 3 : )24(3,4 D
Disposizione di 4
oggetti di classe 4 : )24(4,4 D
Es. Consideriamo il seguente insieme di oggetti astratti:
, , , 4321 aaaa Allora:
Disposizione di 4
oggetti di classe 1 :
Disposizione di 4
oggetti di classe 2 :
)4(1,4 D
)12(2,4 D
5
Disposizioni semplici 3/13
Es. sia n=5 e k=3, come oggetti consideriamo le lettere A,B,C,D,E . Allora si può vedere che ci sono 60 possibili disposizioni (semplici) :
)60(3,5 D
6
Disposizioni / Permutazioni semplici 4/13
In generale vale :
)!(
!)1(....)1(,
kn
nknnnD kn
(*) Nota : per definizione 1!0 1!1
(*)
Es. 1 Quanti numeri di tre cifre (senza ripetizione) si possono formare con 1,2,3,..,9 ?:
5047893,9 D
Es. 2 Ad un concorso di bellezza ci sono 12 partecipanti. Le finaliste sono 4. Quante sono
le possibili graduatorie (contando l’ordine di piazzamento) ?
1188091011124,12 D
Es. 3 (Generalizzando…)
Quanti numeri come es.1 sono dispari ? (8*7*5=280)
Quanti numeri come es.1 sono pari ? (8*7*4=224)
Quanti numeri come es.1 terminano con 9 ? (8*7*1=56)
Quanti numeri come es.1 sono >700 ? (3*8*7=168)
Quanti numeri come es.1 sono <700 ? (6*8*7=336)
7
Disposizioni / Permutazioni semplici 5/13
Def. Permutazione semplice
Si chiama permutazione semplice di n oggetti la disposizione di n oggetti di classe n:
!, nDP nnn
Oss. : Coincide con tutti i possibili ordinamenti degli n oggetti
Es. Permutazioni di 4 lettere:
24!44,44 DP
9
Combinazioni semplici 7/13
Def. Combinazione semplice
Si chiama combinazione semplice di n oggetti di classe k (oppure a k a k) (k≤n) il
numero dei possibili gruppi che si possono formare prendendo k oggetti dagli n oggetti
dati e considerando i gruppi diversi per natura cioè per almeno un elemento ( e non
per l’ordine). Indicheremo tale numero con:
k
nC kn,
Teo. 1
k
kn
knP
D
k
nC
,
,
Teo. 2 )!(!
!
!
)1...()1(
knk
n
k
knnn
k
n
10
n
nnTeo. 3
10
Combinazioni semplici 8/13
Es. In un esperimento: in quanti modi posso scegliere tre animali tra cinque ?
Indichiamo gli animali con le lettere {a,b,c,d,e} si avrà :
10!2!3
!5
3
5
Es. In quanti modi posso estrarre 3 carte da un mazzo di 40 carte ?
9880!3
383940
!37!3
!37383940
!37!3
!40
3
40
Es. Quanti ambi si possono fare con i 90 numeri del lotto? 90 90! 90 89
40052 2! 88! 2
Es. Quanti sono i modi per estrarre due carte di cuori da un mazzo di 40 carte ? 45!8!2
!10
2
10
Es. Quanti gruppi di tre colori si possono formare con i sette colori dell’iride? 353
7
12
Coefficienti binomiali e Binomio di Newton 10/13
Teo. 4
kn
n
k
n
Teo. 5 (formula di Stifel)
k
n
k
n
k
n 1
1
1
Dim.
k
n
kkn
n
knnkn
n
kn
n
)!()!(
!
))!(()!(
!
Oss. Termini equidistanti dagli estremi nel triangolo di Tartaglia sono uguali
Dim.
)!1(!
)!1(
))!1(1()!1(
)!1(1
1
1
knk
n
knk
n
k
n
k
n
)!(!
][)!1(
)!1(!
)!1(
))!()!1(
)!1(
knk
knkn
knk
n
knk
n
k
n
knk
nn
)!()!(
)!1(
13
Coefficienti binomiali e Binomio di Newton 11/13
Teo. 6
Dim.
n
k
n
k
n
0
2
n
k
nn
k
kknn
k
n
k
n
00
21111
14
Disposizioni/Permutazioni con Ripetizione 12/13
Def. Disposizioni con Ripetizione
Si chiama disposizione con ripetizione di n oggetti di classe k (oppure a k a k) (k
qualsiasi) il numero dei possibili gruppi che si possono formare prendendo k oggetti
(eventualmente ripetuti) dagli n oggetti dati e considerando i gruppi diversi per natura o
per ordine. Indicheremo tale numero con
,
( )
n k
RD
Teo. ,
( )
n k
R kD n
Con evidenza di simboli vale: ( ) ( )
,n
R R n
n nP D n
Es. Totocalcio: quante sono le possibili «giocate»?
(13 caselle ciascuna può contenere 1/2/X) 323.594.1313
Es. Permutazioni con ripetizione (oggetti anche uguali):
a) «uno»
b) «Marcito»
c) Permutazioni con elementi uguali «Oro» («oro» , «roo» , «oor»)
d) «Anna» («anna», «anan», «nnaa» , «nana», «naan»)
e) «mamma»
6!3
5040!7
3
!2
!3
6
!2!2
!4
10
!2!3
!5
Se gli n oggetti sono
tutti diversi tra loro
15
Permutazioni con Ripetizione 12bis/13
Formula Generale Permutazioni con ripetizione (anche con oggetti uguali)
Consideriamo l’insieme degli n elementi : 1 2, ,..., na a a
Ciascuno ripetuto, rispettivamente : 1 2, ,..., nk k k volte
Allora, indicato :
1
( )
/ ,....,
1
!
! ...... !n
R
n k k
n
nP
k k
1 .... nn k k
Abbiamo :
17
Combinazioni con Ripetizione 13/13
Def. Combinazioni con Ripetizione
Si chiama combinazione con ripetizione di n oggetti di classe k (oppure a k a k) (k
qualsiasi) il numero dei possibili gruppi che si possono formare prendendo k oggetti
(eventualmente ripetuti) dagli n oggetti dati e non considerando l’ordine.
Indicheremo tale numero con
,
( )
n k
RC
Teo.
k
knC R
kn
1,
Es. Un fabbrica di vernici produce barattoli da 1l, miscelando 10 misurini da una decilitro di
tre diversi colori. Quante sono le tonalità cromatiche ottenibile?
662
12
10
12
10
110310,3
RC
Invece con 100 misurini da 1 centilitro ?
51512
101102
100
102
100
11003100,3
RC
,
( )1
n k
Rn k
Ck
18
Combinatorio nelle Statistiche Classiche e Quantistiche: 1/
Premessa: Particelle Identiche (Indistinguibili)
In fisica statistica particelle identiche ovvero particelle indistinguibili sono particelle che non
possono essere per principio distinte le une alle altre. Questo fatto ha
importanti conseguenze in meccanica statistica. Infatti il calcolo di proprietà in meccanica
statistica si basa su argomenti probabilistici che a loro volta sono influenzati dal fatto che gli
oggetti studiati siano identici o invece esista la possibilità, almeno in linea di principio, di riuscire a
distinguerli.
Come conseguenza, particelle identiche manifestano un comportamento sensibilmente
differente da particelle che possano essere distinte.
Ci sono due modi per distinguere le particelle: il primo metodo si basa su differenze intrinseche
nelle proprietà fisiche delle particelle, quali la massa, la carica elettrica o lo spin. Se le particelle
differiscono in almeno una delle proprietà fisiche intrinseche, esse possono essere distinte
misurando la proprietà in questione. Un elettrone potrà sempre essere distinto da un protone per
via della sua massa molto più leggera, della sua carica di segno opposto.
Tuttavia particelle microscopiche della stessa specie hanno proprietà fisiche completamente
identiche. Tutti gli elettroni dell'universo hanno esattamente la stessa massa, carica elettrica e
spin.
Anche se le particelle hanno proprietà fisiche intrinseche identiche, c'è in linea di principio un
secondo metodo che ci potrebbe permettere di distinguere particelle consistente nel seguire la
traiettoria di ogni particella.
Fintantoché possiamo misurare la posizione di ogni particella con infinita precisione (anche
quando le particelle si trovano a passare molto vicino o addirittura collidono) non ci sarebbe
ambiguità nell'attribuire quale particella è quale.
19
Combinatorio nelle Statistiche Classiche e Quantistiche: 2/
Il problema è che questo approccio non può essere mantenuto nel quadro della meccanica
quantistica. Infatti in meccanica quantistica, le particelle non posseggono una posizione definita
durante il periodo fra due misure della loro posizione. In sostanza, non è possibile per
una particella tracciare una traiettoria ben definita fra due posizioni nelle quali abbiamo
misurato la presenza della particella in due istanti di tempo. Dunque non è possibile
seguire la traiettoria di una particella.
E questo rende in linea di principio le particelle del tutto indistinguibili.
In fisica statistica particelle identiche ovvero particelle indistinguibili sono particelle che non
possono essere per principio distinte le une alle altre. Questo fatto ha importanti conseguenze
in meccanica statistica. Infatti il calcolo di proprietà in meccanica statistica si basa su argomenti
probabilistici che a loro volta sono influenzati dal fatto che gli oggetti studiati siano identici o
invece esista la possibilità, almeno in linea di principio, di riuscire a distinguerli.
Come conseguenza, particelle identiche manifestano un comportamento sensibilmente
differente da particelle che possano essere distinte.
Cammini seguiti da due particelle indistinguibili.
20
Combinatorio nella Statistica Maxwell-Boltzmann: 3/
Nelle statistiche sia classiche (Maxwell-Boltzmann) che quantistiche (Fermi-Dirac, Bose-Einstein) il
discorso iniziale coinvolge la distribuzione (ed il calcolo dei modi in cui questa distribuzione si può
realizzare) di n particelle con caratteristiche diverse rispetto ad g stati di energia disponibili (si pensi
ad es. ai livelli energetici di un atomo).
Statistica di Maxwell-Boltzmann: Particelle Distinguibili (particelle che costituiscono i gas perfetti dei modelli classici)
Vediamo come le tre statiche affrontano il combinatorio considerando 2 particelle (n=2) e 3 stati
energetici disponibili (g=3)
nR gDng
,
21
Combinatorio nella Statistica Bose-Einstein: 4/
Statistica di Bose-Einstein: Particelle Indistinguibili che possono occupare lo stesso livello energetico (tali particelle sono note come BOSONI e sono caratterizzate dall’avere spin intero, ad es. il fotone)
n
gnCR
ng
1,
22
Combinatorio nella Statistica Fermi-Dirac: 4/
Statistica di Fermi-Dirac: Particelle Indistinguibili che NON possono occupare lo stesso livello energetico
(Principio di esclusione di Pauli) (tali particelle sono note come FERMIONI e sono caratterizzate dall’avere spin semi-intero, ad es.
elettrone, protone)
n
gC ng ,