Lezione del 16/12/2009Stage di Treviso Progetto Olimpiadi Combinatoria

Combinatoria

Lezione del 16/12/2009

Stage di Treviso 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?

• Quanti sono i modi di estrarre 1 pallina rossa e

2 palline gialle da un sacchetto che contiene 5

palline rosse, 4 gialle e 6 blu?

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

Colorazioni

• Quando abbiamo a che fare con grafi, tabelle, scacchiere, è utile ricorrere alle “colorazioni”

• ES: da una scacchiera standard 8x8 si tolgono la casella in un angolo e quella opposta. È possibile ricoprire ora la scacchiera con tasselli 2x1?

• NO, in quanto colorando “a scacchiera” tali

tasselli occupano sempre una casella bianca e una nera, quindi il ricoprimento può essere

possibile solo se le caselle nere sono in numero uguale a quelle bianche, ma nel nostro caso

abbiamo tolto 2 caselle dello stesso colore.

Un commesso viaggiatore deve girare tutte le città della regione partendo da A e tornando ad A. I collegamenti in linea continua sono le ferrovie e il biglietto costa 150 euro, i collegamenti tratteggiati sono gli aerei e costano 250 euro.

Quanto spenderà al minimo il commesso viaggiatore?

Invarianti

• L’invariante è una quantità che non cambia

• Esempio: su una lavagna sono scritti 10

numeri. Ad ogni turno si aggiunge 1 ad un numero e si toglie 1 da un altro. Invariante:

somma dei numeri

• Esempio: su una lavagna sono scritti 10

numeri. Ad ogni turno si aggiunge o si toglie 1

da 2 numeri. Invariante: parità della somma

dei numeri.

• Esercizio di esempio:

• Ci sono 3 scatole contenenti molte palline. Ad ogni mossa si può o togliere una pallina da

ogni scatola o prendere 2 palline da una

scatola e metterne una in ciascuna delle altre

due. Qual è l’invariante?

• Antonio e Bernardo giocano al seguente gioco:

sono date due pile di gettoni, una con m gettoni e l'altra con n gettoni. Ogni giocatore sceglie a

turno una delle seguenti mosse:

• prendere un gettone da una delle pile;

• prendere un gettone da ciascuna delle pile;

• spostare un gettone da una pila ad un'altra.

• Perde chi non può più muovere. Comincia

Antonio. Determinare, in funzione di m ed n, se

uno dei due giocatori ha una strategia vincente, e

in caso affermativo specicare di quale giocatore si

tratta.

• Su un’isola ci sono furfanti e cavalieri. In tutto sono 2003. Il primo giorno si riuniscono

attorno a una tavola rotonda e ciascuno dice:

“entrambi i miei vicini sono furfanti”. Il

secondo giorno una persona si è ammalata e i presenti attorno alla tavola sono quindi 2002, e ciascuno afferma: “entrambi i miei vicini

sono della categoria opposta alla mia”. Il

malato era un furfante i un cavaliere?