INTRO

COMBINATORIA E PROBABILITA’

Liceo Scientifico “G. Salvemini” Corso di preparazione per la gara provinciale delle

OLIMPIADI DELLA MATEMATICA

CALCOLO COMBINATORIO

Il Calcolo Combinatorio è lo studio dei diversi modi di ordinare o estrarre oggetti.

Esempi di problemi risolvibili con il CALCOLO COMBINATORIO

QUANTI SONO I TERNI AL LOTTO ?

IN QUANTI MODI DIVERSI SI POSSONO SEDERE GLI INVITATI AD UNA CENA?

QUANTE PAROLE SI POSSONO FORMARE CON LE LETTERE DI “ROMA” ?

QUANTE DELEGAZIONI DI 4 ALUNNI SI POSSONO FORMARE IN UNA CLASSE DI 20 ALUNNI ?

ECC..

QUESITO

SUGGERIMENTO

L’ultima cifra è sicuramente pari. Distinguiamo a seconda se questa sia quella doppia o no. Contiamo, nei due casi, quante sono le possibili posizioni delle due cifre pari uguali e quella della cifra dispari. Otteniamo i casi possibili che vanno moltiplicati per le possibili combinazioni al variare delle cifre..

SOLUZIONE

L’ultima cifra è sicuramente pari. Distinguiamo a seconda se questa sia quella doppia o no. Nel primo caso l’altra cifra doppia può occupare 3 diverse posizioni (non la 4) e per ciascuna di queste la cifra dispari può occupare una qualunque delle 3 posizioni rimanenti. Nel secondo caso le due cifre uguali possono disporsi in 3 modi diversi (1 e 3, 1 e 4, 2 e 4) e per ciascuno di questi la cifra dispari può occupare 2 posizioni tra le 3 libere (non la 5). In tutto si hanno 33 + 32 = 15 modi di fissare le posizioni delle due cifre uguali e della cifra dispari. Per ciascuno di questi modi si possono scegliere liberamente la cifra dispari (5 casi), la cifra pari doppia (5 casi), la prima e la seconda delle cifre pari singole (4 e 3 casi rispettivamente), per un totale di 155543 = 4500 combinazioni differenti che rispettano le richieste.

DISPOSIZIONI SEMPLICI

Dati n oggetti distinti, si dicono disposizioni semplici di classe k ( n), tutte le possibili file che si possono formare con k degli n oggetti, considerando distinte due file che differiscono per l’ordine o per qualche

elemento (gli oggetti non si possono ripetere)

disposizioni di n oggetti a k a k

Dn,k = n·(n-1)·…·(n-k+1)

Esempio

In una gara con 8 atleti quanti sono i possibili ordini di arrivo ?

D8,3 = 8·7·6 = 336

Dn,k = n·(n-1)·…·(n-k+1)

Esempi

D4,2 = 4·3 = 12

Quanti numeri di 2 cifre si possono scrivere con 4 cifre (senza ripeterle) ?

Quante squadre può formare un allenatore che ha a disposizione una

rosa di 18 giocatori ? (nell’ipotesi che ogni giocatore possa

occupare un ruolo qualsiasi)

D18,11 = 18·17·16·15.. ·9·8 = 1.270.312.243.200

Il mestiere di allenatore non sembra agevole!

PERMUTAZIONI SEMPLICI

Le permutazioni sono le disposizioni di n oggetti a n a n

Pn = Dn,n = n·(n-1)·…·2·1 Il prodotto dei numeri da 1 ad n si chiama

n fattoriale e si indica con n!

Pn = n!

0! = 1

Esempi Quanti sono gli anagrammi della parola

AMORE ?

Quanti numeri di 4 cifre si possono scrivere con 4 cifre (senza ripeterle) ?

Quante sono le possibili configurazioni nelle assegnazioni dei posti di una classe di 15 alunni ?

P5 = 5! = 5·4·3·2·1 = 120

P4 = 4! = 4·3·2·1 = 24

P15 = 15! = 1.307.674.368.000

PERMUTAZIONI CON RIPETIZIONE DI OGGETTI

Dati n oggetti in cui k di essi (k<n) si ripetono r1,r2, .. rk volte,

calcoliamo con la seguente formula il numero della permutazioni

tenendo conto che lo scambio di posizione tra oggetti uguale rende equivalente la permutazione:

Prn= !!..!

!

21 krrr

n

Esempi

Quanti sono gli anagrammi della parola MATTATOIO ? (anche di senso non compiuto)

Pr9 = 120.15987654!3

987654!3

!2!2!3

!9

Quanti numeri si possono formare con le cifre 1223334444 ?

Pr10 = 600.12109475!4!3!2

1098765!4

!4!3!2

!10

COMBINAZIONI SEMPLICI

Dati n oggetti distinti, si dicono combinazioni semplici di classe k ( n), tutte i possibili gruppi che si possono formare con k degli n oggetti, considerando distinti due gruppi se differiscono

per almeno un elemento. (non è importante l’ordine e gli oggetti non si possono ripetere)

combinazioni di n oggetti a k a k

Cn,k= =

Coefficiente binomiale

Esempio

Quanti sono i possibili terni all’estrazione del lotto?

C90,3= =

= = 117.480 15

=

Esempio

= 190 10

Quante sono le possibili coppie di rappresentanti di una classe di 20

alunni?

C20,2= =

File e gruppi con ripetizione

Drn,k = nk

Se nella formazione di file e gruppi è possibile ripetere gli oggetti si usano le seguenti formule:

Crn,k=

Esempio

Quanti numeri di 3 cifre si possono formare con 4 cifre eventualmente ripetendo una cifra ?

Dr4,3 = 43 = 64

Dr4,7 = 47 NB – La formula

Drn,k si può utilizzare anche quando k > n !

Esempio

Mescolando 4 vernici tra di loro, in quantita’ uguali, eventualmente anche

ripetendo uno o più colori, quante gradazioni si possono ottenere ?

Cr4,4= =

= 35

EVENTI ALEATORI

Un EVENTO ALEATORIO è un evento, legato ad un determinato fenomeno,

il cui verificarsi può avere più di un caso

Esempi di eventi aleatori: il lancio di un dado, l’estrazione di un carta da un mazzo, l’estrazione di numeri al lotto, ecc.

ALEATORIO è il risultato del dado lanciato, la carta estratta, il numero estratto.

CALCOLO DELLE PROBABILITA’

Il Calcolo delle probabilità è lo studio degli eventi

aleatori e della previsione del loro verificarsi.

CALCOLO DELLE PROBABILITA’

Si definisce lo SPAZIO DEGLI EVENTI l’insieme di tutti gli eventi aleatori possibili

di un determinato fenomeno.

Uno SPAZIO DEGLI EVENTI può avere anche una dimensione infinita.

Consideriamo soprattutto spazi degli eventi finiti i cui possibili risultati siano determinabili a priori

DEFINIZIONE DI PROBABILITA’

Sia E un evento aleatorio appartenente ad

uno SPAZIO DEGLI EVENTI finito.

Si definisce PROBABILITA’ di E il RAPPORTO tra i

casi favorevoli all’evento e il numero di tutti i casi possibili dello SPAZIO DEGLI EVENTI.

Esempio

Qual’e la probabilità che esca 5 al lancio di un dado ?

P(E1) = 1/6

Qual’e la probabilità che non escano 3 o 5 al lancio di un dado ?

P(E2) = 4/6 = 2/3

Esempio

Qual è la probabilità che esca 7 nel lancio di due dadi ?

1 2 3 4 5 6

1 7

2 7

3 7

4 7

5 7

6 7

P(E) = 6/36 = 1/6

QUESITO

SUGGERIMENTO

La lancetta delle ore è orizzontale se l’orologio segna le 3 o le 9. Per qualsiasi posizione raggiunta prima dell’ultimo lancio abbiamo ..

SOLUZIONE

La lancetta delle ore è orizzontale se l’orologio segna le 3 o le 9. Per qualsiasi posizione raggiunta prima dell’ultimo lancio abbiamo 1 risultato utile su 6 per raggiungere o il 9 (fig 1) o il 3 (fig 2). Quindi la probabilità è 1/6 .

Fig. 1 Fig. 2

QUESITO

SUGGERIMENTO

Si consideri la scacchiera colorata come in figura; un passo della pedina può solo condurla da una casella bianca a una casella grigia, e viceversa: ne consegue che, dopo un numero dispari di passi, ..

SOLUZIONE

Si consideri la scacchiera colorata come in figura; un passo della pedina può solo condurla da una casella bianca a una casella grigia, e viceversa: ne consegue che, dopo un numero dispari di passi, la pedina non può che trovarsi in una delle quattro caselle bianche. Qualunque sia la casella bianca in cui la pedina si trova dopo 11 passi, vi sono 4 caselle che essa può raggiungere con il dodicesimo passo, una sola delle quali è un casella d'angolo. La probabilità che la pedina si trovi in un angolo dopo 12 passi (cos come dopo un qualunque numero positivo pari di passi) e quindi 1/4.

PROBABILITA’ ED INSIEMISTICA

Consideriamo un evento E di uno spazio degli eventi S ed

il suo complementare E. S

E E

p(E) + p(E) = 1 p(E) = 1 – p(E)

p(S) = 1 EVENTO CERTO

p() = 0 EVENTO IMPOSSIBILE

Esempio

Qual è la probabilità che non escano monete uguali nel

lancio di tre monete ?

M1 M2 M3

T T T

T T C

T C T

C T T

C C T

C T C

C T T

C C C

P(E) = 1 – P(E) = 1 - 2/8 = 3/4

UNIONE ED INTERSEZIONE DI EVENTI

p(E1 E2) = p(E1) + p(E2) – p(E1 E2)

S

E1 E2

Due eventi sono incompatibili se

E1 E2 =

S

E1 E2

p(E1 E2) = p(E1) + p(E1)

Esempio

Qual è la probabilità che estraendo una carta da un mazzo di 52 carte sia una figura o una carta di cuore ?

E1 = “Si estrae una figura” (12 possibilità)

E2 = “Si estrae una carta di cuori” (13 possibilità)

E1 E2 = “Figure di cuori” (3 possibilità)

P(E1 E2) = P(E1 ) + P(E2) – P(E1 E2) =

12/52 + 13/52 – 3/52 = 22/52 = 11/26

PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI

Due eventi si dicono indipendenti se il verificarsi dell’uno non condiziona il verificarsi dell’altro

Ad esempio l’estrazione di squadre per un sorteggio di coppa.

Ad esempio l’estrazione successiva di carte da un mazzo con reinserimento.

PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI

Si può facilmente dimostrare che se due eventi sono indipendenti vale:

P(E1 E2) = P(E1 ) · P(E2)

PROBABILITA’ COMPOSTA – EVENTI INDIPENDENTI

Qual è la probabilità che due squadre inserite in due urne distinte di 4 squadre siano estratte insieme ?

Qual è la probabilità che in tre estrazioni successive con

reinserimento siano estratti 3 assi ?

P(E1 E2) = P(E1 ) · P(E2) = 1/4 ·1/4 = 1/16

P(E1 E2 E3) = P(E1 ) · P(E2) · P(E3) = 1/13 ·1/13 ·1/13 = 1/2197

QUESITO

Matteo deve fare un test a crocette con 11 domande. Ciascuna domanda ha una sola risposta giusta. La prima domanda ha 2 possibili risposte (A e B), la seconda domanda ha 3 possibili risposte (A, B, C), e così via, fino all'undicesima domanda che ha 12 possibili risposte. Qual è la probabilità che facendo a caso il test Matteo dia almeno una risposta giusta ?

SUGGERIMENTO

Matteo deve fare un test a crocette con 11 domande. Ciascuna domanda ha una sola risposta giusta. La prima domanda ha 2 possibili risposte (A e B), la seconda domanda ha 3 possibili risposte (A, B, C), e così via, fino all'undicesima domanda che ha 12 possibili risposte. Qual è la probabilità che facendo a caso il test Matteo dia almeno una risposta giusta ?

SOLUZIONE

Matteo deve fare un test a crocette con 11 domande. Ciascuna domanda ha una sola risposta giusta. La prima domanda ha 2 possibili risposte (A e B), la seconda domanda ha 3 possibili risposte (A, B, C), e così via, fino all'undicesima domanda che ha 12 possibili risposte. Qual è la probabilità che facendo a caso il test Matteo dia almeno una risposta giusta ?

PROBABILITA’ CONDIZIONALE

In altri casi il verificarsi di un evento dipende dal verificarsi di un altro.

Ad esempio qual è la probabilità che estratto un asso da un mazzo se ne

estragga un altro ?

P(E/F) = 3/51

F = Si estrae il primo asso dal mazzo

E = Si estrae il secondo asso dal mazzo senza reinserire il primo

PROBABILITA’ DI E DATO F

PROBABILITA’ CONDIZIONALE

Vale:

Esempio: Si deve sorteggiare un alunno con un profitto almeno discreto di una classe di 25 alunni. La classe è

composta da 10 ragazze tra le quali 6 alunne su un totale di 13 alunni con profitto almeno discreto.

Qual è la probabilità di scegliere una ragazza ?

P(Estrarre una ragazza / Scelto un alunno con profitto almeno discreto) =

INTERSEZIONE DI EVENTI DIPENDENTI Dalla formula della probabilità condizionale si può ricavare:

P(E F) = P(F) · P(E / F)

Esempio: Qual è la probabilità che da un mazzo di carte siano estratte due figure

(senza reinserire la prima carta) ?

F = Si estrae la prima figura dal mazzo

E = Si estrae la seconda figura dal mazzo senza reinserire la prima

P(E/F) = 11 / 51 P(E F) = P(F) · P(E / F) =

3/13 · 11/51 = 11/221

PROVE RIPETUTE

Consideriamo una evento aleatorio che si ripete n volte.

Sia p la probabilità che l’evento abbia risultato E

La probabilità che E si verifichi k volte su n è:

QUESITO

SUGGERIMENTO

Considera separatamente i casi in cui Nicola abbia rispettivamente perso e vinto l’ultima partita. Nel primo caso (che avviene con probabilità 1/3) Nicola deve aver vinto le prime quattro partite .. Nel secondo caso (che avviene con probabilità 2/3), Nicola deve non aver perso più di due partite tra le prime quattro: quest’ultimo evento ha probabilità complementare rispetto a quella di perdere tutte le prime quattro partite, o di vincerne esattamente una su quattro ..

SOLUZIONE

QUESITO A RISPOSTA NUMERICA

Un cavallo è posto in una casella d'angolo di una scacchiera 3 x 3. Una mossa consiste nello spostare il cavallo in una casella raggiungibile mediante due passi in orizzontale seguiti da un passo in verticale, o due passi in verticale seguiti da un passo in orizzontale. In quanti modi è possibile spostarlo nella casella d'angolo opposta, con esattamente 12 mosse?

SUGGERIMENTO

Osserviamo che il cavallo si muoverà sempre su caselle adiacenti al perimetro della scacchiera (tutte tranne quella centrale) e che da ogni casella sono possibili due mosse: una che porta il cavallo avanti di 3 caselle sul perimetro in senso orario, e una che lo sposta di 3 caselle in senso antiorario.

Se si numerano le caselle del perimetro della scacchiera da 1 a 8 in senso orario, dove la casella 1 è quella di partenza, le mosse del cavallo possono essere rappresentate come nella figura che segue: ciascuna mossa porta il cavallo dal vertice dell'ottagono corrispondente alla casella in cui si trova a uno dei due adiacenti, a seconda che sia in senso orario o antiorario.

Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4 posizioni sull'ottagono, più eventualmente di un numero intero di giri dell'ottagono (8 mosse in senso orario o antiorario riportano il cavallo sulla casella di partenza). Sia x il numero di mosse effettuate in senso orario, y il numero di mosse effettuate in senso antiorario; dobbiamo contare il numero di percorsi possibili in cui x + y = 12 (si compiono 12 mosse in totale) e x - y è un numero della forma 8k+4 (con k intero) ..

SOLUZIONE

Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4 posizioni sull'ottagono, più eventualmente di un numero intero di giri dell'ottagono (8 mosse in senso orario o antiorario riportano il cavallo sulla casella di partenza).

Per arrivare all'angolo opposto, il cavallo deve spostarsi in totale di 4 posizioni sull'ottagono, più eventualmente di un numero intero di giri dell'ottagono (8 mosse in senso orario o antiorario riportano il cavallo sulla casella di partenza). Sia x il numero di mosse effettuate in senso orario, y il numero di mosse effettuate in senso antiorario; dobbiamo contare il numero di percorsi possibili in cui x + y = 12 (si compiono 12 mosse in totale) e x - y è un numero della forma 8k+4 (con k intero). Le coppie ordinate di soluzioni possibili (con x e y non negativi) sono le seguenti: x = 12, y = 0; x = 0, y = 12; x = 8, y = 4; x = 4, y = 8. Le prime due coppie rappresentano i due percorsi in cui il cavallo fa tutte le mosse in senso orario o antiorario. Le altre due coppie rappresentano percorsi in cui vengono fatte 8 mosse in senso orario e 4 in senso antiorario, o viceversa; il numero di tali percorsi è dato dal numero di modi in cui è possibile scegliere l'ordine delle mosse: in particolare, si tratta di in entrambi i casi (fra le 12 mosse da effettuarsi, dalla prima alla dodicesima, vanno scelte le 4 che saranno svolte in senso antiorario nel primo caso, orario nel secondo).