Calcolo combinatorio
elementare
mediante immagini
e poche formule…
Nota per fattoriale !
0! = 1
1! = 1
2! = 1*2 =2
3! = 1*2*3 =6
4! = 1*2*3*4 = 24
5! = 1*2*3*4*5 = 120
Sia n il numero di oggetti tra loro distinguibili A, B C D ..
Sia K un numero intero positivo minore o uguale a n
Disposizione semplice : gruppi di oggetti contenente k oggetti
in modo che ogni gruppo differisca dagli altri o per qualche oggetto
o per l’ordine secondo il quale vengono considerati
N = 4 : A, B, C , D
n ! / (n-1)! = 4! / (4-1)! = 1*2*3*4 / 1*2*3 = 24/6 = 4
Gruppi(1:1) :4
A, B,
AB
D
Calcolo delle disposizioni in funzione di n, k
Varia ordine
AB
C,
Gruppi(2:2) :3 * 4 = 12
BA
AB
AC
AD
CA
BA
BC
BD
CA
CB
CD
DA
DB
DC
Variano oggetti
n ! /(n-2)! = 4! / (4-2)! = 1*2*3*4 / 1*2 = 24/2 = 12
Combinazioni = n! (n-k)!k! = 4! /(4-2)!2! = 1*2*3*4 /2!*2! = 24/4 = 6
AB
AC
AD
BC
BD
CD
N = 4 : A, B, C , D
Gruppi(3:3) : = 24
Combinazioni n! /(n-x)!x! = 4! /(4-3)!3! = 1*2*3*4 /1! *3!= 24/6 = 4
ABC
ABD
ACD
BCD
ABC
ABD
permutazioni
ABC
ACB
BAC
BCA
CAB
CBA
ACD
ADC
CAD
CDA
DAC
DCA
ACD
ABD
ADB
BAD
BDA
DAB
DBA
BCD
BDC
CBD
CDB
DBC
DCB
BCD
n ! / (n-3)! = 4! / (4-3)! = 1*2*3*4 / 1 = 24 =2 4
N = 4 : A, B, C , D
Gruppi(4:4) : = 24
Combinazioni = n! /(n-k)!k! = 4! / (4-4)!4! = 24 / 0!24 = 1
ABCD
permutazioni
n ! / (n-4)! = 4! / (4-4)! = 1*2*3*4 / 0! = 24/1 =2 4
ABCD
ACBD
BACD
BCAD
CABD
CBAD
ACDB
ADCB
CADB
CDAB
DACB
DCAB
ABDC
ADBC
BADC
BDAC
DABC
DBAC
BCDA
BDCA
CBDA
CDBA
DBCA
DCBA
Combinazioni:
gruppi di oggetti con lo stesso numero di elementi
dello stesso tipo,con la stessa frequenza,
indipendentemente dalla loro disposizione
AAB
BAA
Combinazione unica
ABA
Permutazioni:
gruppi di oggetti con lo stesso numero di elementi
con tipo e frequenza variabile: se tipo e frequenza uguali,
deve essere diversa la posizione
AAB
BAA
ABB
ABC
Permutazioni quattro
n=4 ; k=3 quattro lettere prese 3 a 3
ABC
A,B,C,D
ABC
CBA
ACB
BCA
CAB
BAC
Permutazioni = k! = 3! = 6
1 combinazione > 6 permutazioni
AAB
AAB
BAA
ABA
BAB
BBA
ABB
Combinazioni = n! /(n-k)!k! = 24 / 6 = 4
Numero totale permutazioni = 4 * 6 = 24
n ! / (n-k)! 4! /(4-3)! = 24
Numero oggetti n = 4 ; k = 3 :quattro oggetti scelti 3 a 3
Numero combinazioni = n ! / (n-k)!k! = 1*2*3*4 / 1!*1*2*3 = 24/6 = 4
Numero permutazione per data combinazione = k! = 3! = 1*2*3 = 6
Numero permutazioni totale = n! / (n-k)! = 1*2*3*4 / (1!) = 24
Numero permutazioni totale = numero combinazioni * k! = 4 * 1*2*3 = 24
ABCD
ABC
ABD
ACD
BCD
6 permutazioni
6 permutazioni
6 permutazioni
6 permutazioni
24 permutazioni
Permutazione semplice di n oggetti: ogni gruppo contiene tutti gli
elementi :cambia solo la disposizione tra gli oggetti
numero permutazioni semplici = n !
n=3 k=n
Pn = n! /(n-k)! = 1*2*3 /(0!) = 6/1 = 6
Pn = n! = 3! = 1*2*3 = 6
ABC
ABC
CBA
ACB
BCA
CAB
BAC
1,2,3
123
321
132
231
312
213
ROMA
ROMA
AMOR
RAMO
OMAR
RAOM
MOAR
ecc.
Anagrammi…
P4= 4! = 1*2*3*4 = 24
Combinazioni semplici : gruppi contenenti lo stesso numero di oggetti
con almeno uno diverso rispetto ad ogni altro gruppo
N oggetti : A, B, C, D , k=2
AB
AC
AD
BC
BD
CD
n=4 ; k=2
(4 su 2)= 4(4-2+1)/2! = 4*3/2 = 6
6 combinazioni
Numero di combinazioni semplici di n oggetti
distinti di classe k
( n su k) = n * k / k!
(n su k) = n (n-1)(n-2)(n-3)..(n-k+1 ) / k!
n = 5; k = 2
n=9 ; k=3
n=7 ; k=5
(5 su 2)= 5(5-2+1) / 2! = 10
(9 su 3)= 9(9-1)(9-3+1) / 3! = 9*8*7/6 = 84
(7 su 5)= 7(7-1)(7-2)(7-3)(7-5+1) / 5! = 7*6*5*4*3 / 120 = 21
Riposo…
Composizione : stessi oggetti senza ordine preciso di uscita:
sono equivalenti
permutazioni : stessi oggetti con ordine preciso di uscita:
non sono equivalenti
Uscita senza precedenze, ordine.combinazione
Uscita secondo precedenza, ordine:permutazione
6 cifre (1,2,3,4,5,6) :quanti numeri interi con tre cifre sono possibili ?
n=6 ; k=3
P(n,k) = (n su k) = (6 su 3) = n(n-1)(n-2)(n-k+1)= 6*5*4=120
Con colori rosso, verde, bianco, giallo, quante bandiere tricolori possibili?
n =4 ; k=3
P(n,k)=(n su k) = (4 su 3) = n(n-1)(n-k+1)=4*3*2= 24
In quanti modi 4 persone possono occupare 5 posti numerati ?
n=5 ; k= 4
P(n,k)= (n su k) = (5 su 4) = n(n-1)(n-2)(n-k+1)= 5*4*3*2=120
Numero di anagrammi possibile con parola napoli ?
n= 6
Pn = n! 6! = 1*2*3*4*5*6 = 720
In quanti modi possibile coprire 3 teste con 5 cappelli ?
n=5 ; k =3
P(n,k)= (n su k) = (5 su 3) = 5(n-1)(n-k+1)=5*4*3 = 60
Con 90 numeri, quanti ambi, quanti terni sono possibili?
n =90 ; k1= 2 ; k2 =3
P(n,k1)=(n su k1)=(90 su 2)=n(n-k1+1)/k1! =90*89/2 = 4005
P(n,k2)=(n su k2)=(90 su 3)=n(n-1)(n-k2+1)/k2! = 90*89*88/6 = 117480
Dati i numeri 1,3,4 quanti numeri ( di 3 cifre) cominciano con 3?
n = 3 ; Pn = n! = 3! = 6
134, 143, 431, 413, 314, 341
In quanti modi diversi 3 persone possono occupare 3 su 4 posti ?
n=4 ; k=3
P(n.k)=(n su k)= (4 su 3) = n(n-1)(n-k+1)=4*3*2=24
Con 7 giocatori disponibili, quante linee di attacco con 5 sono possibili?
n=7 ;k =5
P(n,k)=(n su k)=(7 su 5)= n(n-1)(n-2)(n-3)(n-k+1)=7*6*5*4*3=2520
Quanti sono i numeri di 5 cifre diverse (esclusi 0, 3, 6 )?
n=7;k=5
p(n,k)=(n su k)=(7 su 5) = n(n-1)(n-2)(n-3)(n-k+1)=7*6*5*4*3=2520
5 punti su un piano, e mai 3 allineati: quanti triangoli sono possibili?
n = 5; k=2
P(n,k)=(n su k)=n(n-k+1)/k! = 5*4/2 = 10
A
B
E
C
D
ACB
ADC
ABD
BCD
AED
BED
CED
BEA
CEB
CEA
4 palline distinte come possono occupare i vertici di un quadrato?
n=4;k=4
Pn = n! = 4! = 1*2*3*4 =24
ABCD
ACBD
BACD
BCAD
CABD
CBAD
ABDC
ADBC
BADC
BDAC
DABC
DBAC
ACDB
ADCD
CADB
CDAB
DACB
DCAB
BCDA
BDCA
CBDA
CDBA
DBCA
DCBA
ABCD
BCAD
ACBD
BACD
Esempi con immagini
per descrivere
associazioni varie
combinazioni, permutazioni
con numero oggetti e classi
variabili
Permutazione: insieme di x oggetti ordinati estratti da n oggetti
combinazione: insieme di x oggetti ,non ordinati, estratti da n oggetti
Numero di permutazioni Px = n ! / (n-x)!
Numero di combinazioni Cx = n! /(n-x)!x!
Dati n oggetti (A, B, C) determinare le possibili associazioni
permutazioni e combinazioni, prendendo due oggetti per volta
n=3 ; x = 2
P2 = 3 ! / (3-2)!
= 1*2*3 /1 ! = 6
C2 = 3 ! / (3-2)!2! = 1*2*3 /1! 2! = 6 /1*1*2 = 6 / 2 = 3
A,B,C
AB
AB
BA
AC
AC
CA
BC
CB
BC
6 permutazioni
3 combinazioni
Numero di permutazioni Px = n ! / (n-x)!
Numero di combinazioni Cx = n! /(n-x)!x!
Oggetti n = 4; presi 3 per volta x=3
P3= 4 ! / (4-3) ! =1*2*3*4 / (1 !) = 24
C3= 4 ! /(4-3)!3!=1*2*3*4 / (1 !)*1*2*3 = 24 /6 = 4
A, B, C, D
A
B
C
A
C
B
B B
A C
C A
ABC
C C
A B
B A
A A
B D
D B
B B
A D
D A
ABD
A A
D D C D
A B D C
B A
C C
A D
D A
ACD
4 combinazioni
24 permutazioni
D
A
C
D
C
A
B
C
D
B C C D
D B D B
C D B C
BCD
D
C
B
numero oggetti = n
numero oggetti per combinazione = x
numero di combinazioni = nCx
numero permutazioni per ogni combinazione = x !
Numero totale permutazioni = nCx * x !
Oggetti n = 4; presi 3 per volta x=3
A, B, C, D
A
B
C
A
C
B
B B
A C
C A
ABC
C C
A B
B A
A A
B D
D B
B B
A D
D A
ABD
4 combinazioni
A A
D D C D
A B D C
B A
C C
A D
D A
D
A
C
D
C
A
B
C
D
B C C D
D B D B
C D B C
ACD
24 permutazioni
BCD
n=4
x=3
nCx = n ! / (n-x)!x! = 1*2*3*4 / (4-3)!3! = 24 / 1! * 1*2*3 =24/6 = 4
nPx = x ! = 3 ! = 1*2*3 = 6
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
D
C
B
Oggetti n = 4; presi 3 per volta x=3
Disegnare diagramma ad albero
Contare le combinazioni :4
Contare permutazioni per ogni combinazione : 6
Contare permutazioni totali : 4 * 6 = 24
n ! / ( n – k)! = 4 ! / (4-3)! = 1*2*3*4 / 1 = 24
A, B, C, D
4 combinazioni
A
B
C
A
C
B
B B
A C
C A
ABC
C C
A B
B A
24 permutazioni
A A
B D
D B
B B
A D
D A
ABD
A A
D D C D
A B D C
B A
C C
A D
D A
D
A
C
D
C
A
B
C
D
B C C D
D B D B
C D B C
ACD
BCD
Numero combinazioni = n ! (n – x)!x!
nCx = n ! / (n-x)!x! = 1*2*3*4 / (4-3)!3! = 24 / 1! * 1*2*3 =24/6 = 4
con n oggetti e classe x; permutazioni per combinazione = x!
nPx = x ! = 3 ! = 1*2*3 = 6
numero permutazioni totali = numero combinazioni * classe
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
D
C
B
Es. 5 oggetti (A,B,C,D,E) presi a 2 per volta :
n=5; x =2
Numero combinazioni = n! (n-x)!x! = 5! (3!)*2! = 120 /12 = 10
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
Numero permutazioni per classe = x ! = 1*2 =2
AB,BA
AC,CA
AD,DA
AE,EA
BC,CB
BD,DB
BE,EB
CD,DC
CE,EC
DE,ED
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
Numero permutazioni totale = nC * x ! = 10 *2! = 20
Nota :numero combinazioni (5 su 2) = (5 su 3)
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
ABC,ABD,ABE,ACD,ACE,ADE,BCD,BCE,BDE,CDE
5! /(5-2)!2! = 120 /3!*2! = 120 /12 = 10
5! /(5-3)!3! = 120 /2!*3! = 120/12 =10
numero oggetti = n
numero oggetti per combinazione = x
numero di combinazioni = nCx
numero permutazioni per ogni combinazione = x !
Numero totale permutazioni = nCx * x !
n=4
x=3
nCx = n ! / (n-x)!x! = 1*2*3*4 / (4-3)!3! = 24 / 1! * 1*2*3 =24/6 = 4
nPx = x ! = 3 ! = 1*2*3 = 6
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
Alcune formule per facilitare i calcoli
Il codice genetico mette in relazione una sequenza formata da 3
nucleotidi (indicati dalle basi azotate A, C, G, U) con specifici amminoacidi
UUA > leu
AUU > ile
GUU > val
UUG > leu
UCC > ser
CCU > pro
UUA
leu
UUA
leu
AUU
leu
AUU
ile
Si comprende la importanza che assume
una associazione di tre basi considerata
come combinazione
UUA = AUU (contiene 2 U , 1 A)
come permutazione
UUA <> AUU
GUU
val
GUU
val
UUG
val
UUG
leu
UCC
ser
UCC
ser
CCU
ser
CCU
pro
combinazione
permutazione
Nei ribosomi il DNA trasformato in mRNA viene tradotto in proteina
associando ad ogni tripletta (permutazione) il relativo amminoacido
Se ogni tripletta fosse considerata come combinazione , la proteina
tradotta sarebbe diversa da quella codificata nel DNA