Lezione del 04/01/2010Stage di Terni Progetto Olimpiadi Combinatoria

Combinatoria

Lezione del 04/01/2010

Stage di Terni Progetto Olimpiadi

Fattoriali e Binomiali

• Fattoriale: n!=n*(n-1)*(n-2)*…2*1

• 0!=1

• Binomiale (n,k)= n!/(k!(n-k)!)

• I binomiali formano il triangolo di tartaglia e sono i coefficienti del termine k-esimo della potenza ennesima di un binomio

• Es: (a+b) ⁵ =(5,0)a ⁵ + (5,1)a ⁴ b + (5,2)a ³ b ² +

(5,3)a ² b ³ + (5,4)ab ⁴ + (5,5)b ⁵

Permutazioni

• Abbiamo un insieme composto di n elementi distinti fra loro

• Le permutazioni sono i possibili ordinamenti che possiamo dare a questi elementi

• Quante sono?

• Per il primo elemento possiamo scegliere fra tutti gli n elementi, come secondo elemento potremo scegliere fra n-1, ecc

• Si intuisce facilmente che le permutazioni di n

elementi sono n!

• Esempio:

• Calcolare il numero di anagrammi distinti della parola CUORE

• Le lettere sono tutte diverse => sono le permutazioni di 5 elementi distinti => 5!

• E se invece l’insieme contiene degli elementi ripetuti?

• ES: calcolare il numero di anagrammi della parola MATEMATICA

• In questo caso bisogna ricorrere a un “trucchetto”:

consideriamo in un primo momenti tutti gli elementi differenti. Possiamo immaginarci mentalmente di porre un segno che contraddistingua lettere uguali, per

esempio un pedice con un indice

M

A

T

E

M

A

T

I

C

A

• Le permutazioni in questo caso sono 10! (la parola ha 10 lettere)

• Ora bisogna contare il fatto che anagrammi che differiscono per permutazioni di lettere uguali (con indice diverso) sono in realtà indistinguibili:

• M

A

T

E

M

A

T

I

C

A

e M

A

T

E

M

A

T

I

C

A

sono da considerarsi uguali

• Consideriamo singolarmente ogni lettera:

• Ci sono 2 M, se scambio M

con M

non succede nulla

• In generale dato un gruppo di lettere uguali se ne faccio una permutazione la parola resta la stessa

• Quindi ogni anagramma compare un numero di volte pari alle permutazioni di ciascun insieme di lettere uguali

• Nel nostro caso comparirà 2! volte per scambi di M, 3!

Volte per scambi di A e 2! Volte per scambi di T

• Gli anagrammi sono quindi 10!/(2!3!2!)

• Esercizi d’esempio

• Calcola il numero di anagrammi di STAGISTI

• Calcola il numero di anagrammi di ARMATA

Disposizioni

• Torniamo all’insieme con n elementi distinti. Invece di chiederci quanti sono i modi possibili di dare un ordine a tutti gli elementi dell’insieme(permutazioni), possiamo

chiederci quanti sono i modi di dare un ordine a k elementi scelti dall’insieme (con k<n, con k=n si torna al caso delle permutazioni)

• Analogamente a prima possiamo pensare così:

• Diamo un ordine a tutti gli elementi dell’insieme: n!

• Poi però consideriamo solo i primi k elementi delle sequenza ottenuta. Considerando solo i primi k, ogni sequenza risulterà equivalente a molte altre. A quante?

Quante sono le permutazioni degli elementi che non

consideriamo: (n-k)! => D(n,k)= n!/(n-k)!

• Esempio: insieme di 4 numeri 1,2,3,4

• Voglio D(4,2)

• Scrivo tutte le permutazioni:

• 1 2 3 4; 2 1 3 4; 3 1 2 4; 4 1 2 3

• 1 2 4 3; 2 1 4 3; 3 1 4 2; 4 1 3 2

• 1 3 2 4; 2 3 1 4; 3 2 1 4; 4 2 1 3

• 1 3 4 2; 2 3 4 1; 3 2 4 1; 4 2 3 1

• 1 4 2 3; 2 4 1 3; 3 4 1 2; 4 3 1 2

• 1 4 3 2; 2 4 3 1; 3 4 2 1; 4 3 2 1

• Ogni disposizione che per me è differente dalle altre è contrata 2! Volte, cioè il numero di permutazioni degli altri 2 elementi: per esempio per 1 2 è contata 2 volte.

Cioè le permutazioni di 3, 4.

• Caso con ripetizione: voglio sapere in quanti modi posso formare una sequenza lunga k partendo da n elementi differenti ripetendo però anche più volte lo stesso elemento

• Per esempio: combinazione cassaforte a 4 cifre

• Ogni cifra ha 10 possibilità (da 0 a 9)=> 10 ⁴

• In generale sarà n ^k

Combinazioni

• Se mi chiedo quante sono i possibili

sottoinsieme di k elementi di un insieme che contiene n elementi differenti fra loro queste sono le combinazioni C(n,k). In pratica sono le disposizioni a meno dell’ordine.

• Quindi il numero di combinazioni sarà uguale a quelle delle disposizioni fratto il numero di possibili permutazioni dei k elementi scelti:

• C(n,k)=D(n,k)/k!=n!/(k!(n-k)!)= Binomiale (n,k)

• Esempio: in quanti modi è possibile scegliere un gruppo di 5 alunni in una classe di 30?

• Risposta: gli alunni sono tutti diversi, l’ordine non conta quindi C(30,5)

• La maestra deve interrogare 5 alunni alla cattedra, uno alla volta. In quanti modi può farlo?

• Risposta: stavolta l’ordine conta quindi sarà

D(30,5)

• Esercizi proposti:

• Vogliamo suddividere una classe di 30 alunni in 6 gruppi da 5. In quanti modi possiamo

farlo?

Inclusione/Esclusione

• Caso 2 insiemi: A U B= A + B - A∩B

• Caso 3 insiemi: A U B U C = A + B + C - A∩B - A∩C - B∩C + A∩B∩C

• Esercizio di esempio:

• In una classe 20 ragazzi giocano a calcio, 15

basket, 7 praticano entrambi gli sport. Quanti

sono i ragazzi nella classe?

Probabilità

• Definizione classica

• P = casi favorevoli/casi possibili

• Esercizio di esempio: quale era la probabilità di estrarre la pallina rossa e le 2 gialle dal

sacchetto nel problema precedente?

• P(A U B) = P(A) + P(B) - P(A∩B)

• P(A ∩ B)= P(A)*P(B|A) = P(B)*P(A|B) dove P(B|A) è la probabilità che si verifichi B

essendosi verificato A

• Nel caso di eventi indipendenti P(B|A) = P(B)

• Esercizio di esempio: rifacciamo l’esercizio della palline usando le formule della

probabilità condizionata