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