Post on 02-May-2015
Calcolo combinatorioelementare
mediante immaginie poche formule…
Nota per fattoriale !0! = 11! = 1
2! = 1*2 =23! = 1*2*3 =6
4! = 1*2*3*4 = 245! = 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
Gruppi(1:1) :4
A, B, C, D
Gruppi(2:2) :3 * 4 = 12
AB
ACAD
BABCBD
CACBCD
DADBDC
n ! / (n-1)! = 4! / (4-1)! = 1*2*3*4 / 1*2*3 = 24/6 = 4
n ! /(n-2)! = 4! / (4-2)! = 1*2*3*4 / 1*2 = 24/2 = 12
AB BA
AB CA
Calcolo delle disposizioni in funzione di n, kVaria ordine
Variano oggetti
Combinazioni = n! (n-k)!k! = 4! /(4-2)!2! = 1*2*3*4 /2!*2! = 24/4 = 6
ABACADBCBDCD
N = 4 : A, B, C , D
Gruppi(3:3) : = 24
n ! / (n-3)! = 4! / (4-3)! = 1*2*3*4 / 1 = 24 =2 4
ABCACBBACBCACABCBA
ABDADBBADBDADABDBA
ACDADCCADCDADACDCA
BCDBDCCBDCDBDBCDCB
ABC
ABD
ACD
BCD
Combinazioni n! /(n-x)!x! = 4! /(4-3)!3! = 1*2*3*4 /1! *3!= 24/6 = 4
permutazioni
ABCABDACDBCD
N = 4 : A, B, C , D
Gruppi(4:4) : = 24
n ! / (n-4)! = 4! / (4-4)! = 1*2*3*4 / 0! = 24/1 =2 4
Combinazioni = n! /(n-k)!k! = 4! / (4-4)!4! = 24 / 0!24 = 1
ABCD
ABCDACBDBACDBCADCABDCBAD
ABDCADBCBADCBDACDABCDBAC
ACDBADCBCADBCDABDACBDCAB
BCDABDCACBDACDBADBCADCBA
permutazioni
Combinazioni: gruppi di oggetti con lo stesso numero di elementi
dello stesso tipo,con la stessa frequenza, indipendentemente dalla loro disposizione
AAB
BAA
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
Combinazione unica
Permutazioni quattro
n=4 ; k=3 quattro lettere prese 3 a 3 A,B,C,D
AABAABBAAABABABBBAABB
1 combinazione > 6 permutazioni
ABC
ABCCBAACBBCACABBAC
Permutazioni = k! = 3! = 6
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 permutazioni totale = n! / (n-k)! = 1*2*3*4 / (1!) = 24
Numero permutazioni totale = numero combinazioni * k! = 4 * 1*2*3 = 24
Numero permutazione per data combinazione = k! = 3! = 1*2*3 = 6
ABCD
ABCABDACDBCD
6 permutazioni
6 permutazioni
6 permutazioni
6 permutazioni
24 permutazioni
Permutazione semplice di n oggetti: ogni gruppo contiene tutti glielementi :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
ABCCBAACBBCACABBAC
1,2,3
123321132231312213
ROMA P4= 4! = 1*2*3*4 = 24
Anagrammi…
ROMAAMORRAMOOMARRAOMMOARecc.
Combinazioni semplici : gruppi contenenti lo stesso numero di oggetti
con almeno uno diverso rispetto ad ogni altro gruppo
ABACADBCBDCD
N oggetti : A, B, C, D , k=2
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 (5 su 2)= 5(5-2+1) / 2! = 10
n=9 ; k=3 (9 su 3)= 9(9-1)(9-3+1) / 3! = 9*8*7/6 = 84
n=7 ; k=5 (7 su 5)= 7(7-1)(7-2)(7-3)(7-5+1) / 5! = 7*6*5*4*3 / 120 = 21
n=4 ; k=2 (4 su 2)= 4(4-2+1)/2! = 4*3/2 = 6
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 = 4005P(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
C
D
E
ACBADCABDBCDAEDBEDCEDBEACEBCEA
4 palline distinte come possono occupare i vertici di un quadrato?n = 4 ; k = 4
Pn = n! = 4! = 1*2*3*4 =24
ABCDACBDBACDBCADCABDCBAD
ABDCADBCBADCBDACDABCDBAC
ACDBADCDCADBCDABDACBDCAB
BCDABDCACBDACDBADBCADCBA
ABCDACBD
BACDBCAD
Esempi con immaginiper descrivere
associazioni variecombinazioni, permutazionicon numero oggetti e classi
variabili
Permutazione: insieme di x oggetti ordinati estratti da n oggetticombinazione: 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 ! = 6C2 = 3 ! / (3-2)!2! = 1*2*3 /1! 2! = 6 /1*1*2 = 6 / 2 = 3
A,B,C
AB BA AC CA BC CB 6 permutazioni
3 combinazioniAB AC BC
Numero di permutazioni Px = n ! / (n-x)!Numero di combinazioni Cx = n! /(n-x)!x!
A, B, C, D
Oggetti n = 4; presi 3 per volta x=3
P3= 4 ! / (4-3) ! =1*2*3*4 / (1 !) = 24C3= 4 ! /(4-3)!3!=1*2*3*4 / (1 !)*1*2*3 = 24 /6 = 4
ABC
ACB
BAC
BCA
CAB
CBA
ABD
ADB
BAD
BDA
DAB
DBA
ACD
ADC
CAD
CDA
DAC
DCA
BCD
BDC
CBD
CDB
DBC
DCB
ABC ABD ACD BCD
4 combinazioni
24 permutazioni
A, B, C, D
Oggetti n = 4; presi 3 per volta x=3
ABC
ACB
BAC
BCA
CAB
CBA
ABD
ADB
BAD
BDA
DAB
DBA
ACD
ADC
CAD
CDA
DAC
DCA
BCD
BDC
CBD
CDB
DBC
DCB
ABC ABD ACDBCD
4 combinazioni 24 permutazioni
numero oggetti = nnumero oggetti per combinazione = x
numero di combinazioni = nCxnumero permutazioni per ogni combinazione = x !
Numero totale permutazioni = nCx * x !
n = 4x = 3
nCx = n ! / (n-x)!x! = 1*2*3*4 / (4-3)!3! = 24 / 1! * 1*2*3 =24/6 = 4nPx = x ! = 3 ! = 1*2*3 = 6
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
A, B, C, D
Oggetti n = 4; presi 3 per volta x=3
ABC
ACB
BAC
BCA
CAB
CBA
ABD
ADB
BAD
BDA
DAB
DBA
ACD
ADC
CAD
CDA
DAC
DCA
BCD
BDC
CBD
CDB
DBC
DCB
ABC ABD ACDBCD
4 combinazioni 24 permutazioni
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 = 4con n oggetti e classe x; permutazioni per combinazione = x!
nPx = x ! = 3 ! = 1*2*3 = 6numero permutazioni totali = numero combinazioni * classe
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
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
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, AC, AD, AE, BC, BD, BE, CD, CE, DEAB,BAAC,CAAD,DAAE,EABC,CBBD,DBBE,EBCD,DCCE,ECDE,ED
Numero permutazioni totale = nC * x ! = 10 *2! = 20
Nota :numero combinazioni (5 su 2) = (5 su 3)
5! /(5-2)!2! = 120 /3!*2! = 120 /12 = 10
5! /(5-3)!3! = 120 /2!*3! = 120/12 =10
ABC,ABD,ABE,ACD,ACE,ADE,BCD,BCE,BDE,CDE
AB, AC, AD, AE, BC, BD, BE, CD, CE, DE
numero oggetti = nnumero oggetti per combinazione = x
numero di combinazioni = nCxnumero permutazioni per ogni combinazione = x !
Numero totale permutazioni = nCx * x !
n = 4x = 3
nCx = n ! / (n-x)!x! = 1*2*3*4 / (4-3)!3! = 24 / 1! * 1*2*3 =24/6 = 4nPx = x ! = 3 ! = 1*2*3 = 6
nP = nCx * x! = 4 * 3! = 4*(1*2*3) = 24
Alcune formule per facilitare i calcoli
UUA > leuAUU > ileGUU > valUUG > leuUCC > serCCU > pro
Il codice genetico mette in relazione una sequenza formata da 3nucleotidi (indicati dalle basi azotate A, C, G, U) con specifici amminoacidi
Si comprende la importanza che assume una associazione di tre basi considerata
come combinazione UUA = AUU (contiene 2 U , 1 A)
come permutazioneUUA <> AUU
UUA AUU GUU UUG UCC CCUleu leu val val ser ser
combinazione
permutazioneUUA AUU GUU UUG UCC CCUleu ile val leu ser pro
Nei ribosomi il DNA trasformato in mRNA viene tradotto in proteinaassociando ad ogni tripletta (permutazione) il relativo amminoacido
Se ogni tripletta fosse considerata come combinazione , la proteinatradotta sarebbe diversa da quella codificata nel DNA