Matematica X - 1 Calcolo combinatorio

Calcolo combinatorio

Il calcolo combinatorio sviluppa degli strumenti per valutare il numero di permutazioni, disposizioni, combinazioni possibili dati un certo numero di oggetti e alcune regole. Per esempio, quante sono le possibilità di compilare una schedina del lotto a numeri? Tratteremo brevemente di questo tipo di calcolo distinguendo dapprima tra

permutazioni, disposizioni e combinazioni.

permutazioni

Parliamo di permutazioni quando dobbiamo contare il numero di possibilità di ordinare un certo numero di oggetti già dati.

Per esempio, quanti diversi numeri posso scrivere utilizzando una volta la cifra 1, una volta la cifra 3 e una volta la cifra 5? Il numero cambia in funzione dell'ordine con cui scrivo queste cifre. Le possibilità sono: 135, 153, 315, 351, 513, 531. Sei diversi numeri. Possiamo fare questo ragionamento: per scegliere chi sta' in prima posizione ho tre possibilità, per ognuna di queste tre possibilità avrò due possibilità di scegliere chi mettere in seconda

posizione, una volta scelto il primo e il secondo non mi resteranno alternative per il terzo. Le possibilità sono dunque 3⋅2⋅1 = 6.

In generale, il numero di possibilità di ordinare n diversi oggetti vale n! e scriveremo:

P n = n⋅(n - 1)⋅(n - 2)⋅ ... ⋅2⋅1 = n!

(ricordiamo che n! si legge "n fattoriale" e indica il prodotto dei primi n numeri interi: n!=1⋅2⋅3⋅...⋅n. Ad esempio 5!

= 1⋅2⋅3⋅4⋅5 = 120. Per definizione si pone 0!=1. Le macchinette lo sanno fare) disposizioni

Parliamo invece di disposizioni quando dobbiamo contare il numero di possibilità scegliere e ordinare un certo numero di oggetti provenienti da un insieme più largo di oggetti.

Per esempio, quanti numeri posso scrivere utilizzando tre diverse cifre? Le cifre che posso utilizzare sono le dieci cifre del sistema decimale ma i numeri che scrivo non devono presentare due volte la stessa cifra. Per scegliere la prima cifra ho 10 possibilità, per ognuna di queste 10 possibilità avrò 9 possibilità di scegliere la seconda cifra e per ognuna di queste 9 possibilità avrò 8 possibilità di scegliere la terza cifra. Così le possibilità sono 10⋅9⋅8 = 720 Il numero di possibilità di scegliere e ordinare r diversi oggetti tratti da un insieme di n oggetti vale:

D n,r = n⋅(n - 1)⋅(n - 2)⋅ ... ⋅(n - r + 1) =

)!

(

! r n

n

−

Troviamo per le disposizioni anche altre notazioni. Sulla mia Texas uso il tasto nPr.

combinazioni

Parleremo di combinazioni quando dovremo contare il numero di possibilità scegliere, senza ordinarli, un certo numero di oggetti provenienti da un insieme più largo di oggetti.

Riprendiamo l'esempio del lotto a numeri; da un insieme di 42 numeri dobbiamo estrarne 6. I numeri vanno dal 1 al 42 (sono tutti diversi) e una volta estratto un numero non lo rimettiamo nell'urna. Inoltre, sebbene li estraiamo uno dopo l'altro, per assegnare il montepremi non ci basiamo sull'ordine con il quale escono dall'urna. Se contasse l'ordine avremmo D 42,6 estrazioni possibili. Se ci fosse da ordinare sei numeri già estratti avremmo P 6 possibilità.

Noi vogliamo estrarre 6 numeri senza che l'ordine conti per cui avremo D 42,6 / P 6 possibilità.

In generale, il numero di possibilità di scegliere r diversi oggetti tratti da un insieme di n oggetti vale:

! )!

(

, !

, n r r

n P

C D

n r n r

n = = −

Troviamo per le disposizioni le notazioni  

 



 r

n o C _r ⁿ già viste alla dispensa numero 22.

Sulla mia Texas uso il tasto nCr.

A quanto detto sulle permutazioni, disposizioni e combinazioni aggiungeremo qualche risultato che riguarda le ripetizioni.

permutazioni con ripetizioni

Parliamo di permutazioni con ripetizioni quando contiamo il numero di possibilità di ordinare un certo numero di oggetti non tutti distinti.

Esempio: quanti diversi numeri posso scrivere utilizzando due volte la cifra 1 e una volta la cifra 3? Le possibilità sono: 131, 113, 311. Solo la metà di quelle calcolate per le cifre 1, 3 e 5.

Altro esempio: quanti diversi numeri posso scrivere utilizzando due volte la cifra 1 e una volta la cifra 3 e tre volte la cifra 5? Le possibilità di ordinare 6 cifre diverse sono P ₆ = 6!. Ma essendoci una volta due cifre uguali e una volta tre cifre uguali le possibilità sono 6! / (2!⋅3!) = 60.

In generale, il numero di possibilità di ordinare n oggetti tra i quali k 1 , k 2 , …, k m sono uguali, vale:

!

!...

!

!

2 1 ...

, _{1 2}

m k

k k

n k k k

P n

m =

disposizioni con ripetizioni

Parliamo di disposizioni con ripetizioni quando dobbiamo contare il numero di possibilità di scegliere e ordinare un certo numero di oggetti provenienti da un insieme ma ogni oggetto può ripetersi quante volte vogliamo.

Per esempio, quanti numeri posso scrivere utilizzando tre cifre? Le cifre che posso utilizzare sono le dieci cifre del sistema decimale e i numeri che scrivo possono presentare più volte la stessa cifra. Per scegliere la prima cifra ho 10 possibilità, per ognuna di queste 10 possibilità avrò 10 possibilità di scegliere la seconda cifra e per ognuna di queste 10 possibilità avrò 10 possibilità di scegliere la terza cifra. Così le possibilità sono 10⋅10⋅10 = 10 ³

Le possibilità di scegliere e ordinare r oggetti, con possibile ripetizione, tratti da un insieme di n oggetti sono:

r r

n n

D ^' _, =

combinazioni con ripetizioni

Quando dobbiamo contare il numero di possibilità di scegliere, senza ordinarli e con possibilità di ripetizione, un certo numero di oggetti provenienti da un insieme di oggetti, parliamo di combinazioni con ripetizioni .

In una pasticceria offrono quattro tipi di pasticcini. Quante diverse possibilità ho di formare un pacchetto di tre paste? Non sto a contarle ma dovrebbero essere 20.

In generale, le possibilità di scegliere r oggetti, con possibile ripetizione, tratti da un insieme di n oggetti sono:

 

 



 + −

− =

−

= +

r r n r n

r

C _{n r} n 1

! )!

1 (

)!

1

' (

,

Esercizi:

1. Quante diverse parole (anagrammi), anche senza senso, posso fare cambiando di posto le lettere della parola MERCATO?

2. Quante diverse parole (anagrammi), anche senza senso, posso fare cambiando di posto le lettere della parola CERCATO?

3. Quante diverse parole di tre lettere, anche senza senso, posso fare utilizzando, senza ripetizione, le lettere della parola MERCATO?

4. Quante diverse parole di quattro lettere, anche senza senso, posso fare utilizzando, con possibili ripetizioni, le lettere della parola MERCATO?

5. In una pasticceria offrono dieci tipi di pasticcini. Quante diverse possibilità ho di formare un pacchetto di quattro paste tutte diverse?

6. In una pasticceria offrono dodici tipi di pasticcini. Quante diverse possibilità ho di formare un pacchetto di

quattro paste con possibilità ripetizione?

Probabilità (vedi anche Bergamini modulo M unità 2)

Il calcolo delle probabilità sviluppa degli strumenti per poter formulare delle previsioni riguardanti eventi futuri sulla base delle conoscenze a disposizione. Può utilizzare il calcolo combinatorio per contare gli eventi possibili e/o favorevoli. Per esempio, che probabilità ho di fare sei al lotto con una schedina? E di fare cinque?

S = Spazio campione

Lo spazio campione o spazio dei campioni è l'insieme dei risultati possibili di un esperimento e ciascun risultato è detto punto campione. Uno spazio campione è detto discreto se possiede un numero finito di punti o se questi sono numerabili (come l'insieme dei numeri naturali). Invece è detto continuo se non è numerabile (come ).

Evento

Un evento A è un sottoinsieme dello spazio campione S. Un evento è un insieme di risultati possibili. Un evento consistente in un solo punto è detto evento elementare. L'insieme vuoto ∅ è pure un evento, in questo caso si parla di evento impossibile. Anche S è un evento; l'evento certo. Se il risultato di un esperimento è un elemento di A, diremo che l'evento A si è verificato.

Eventi incompatibili (disgiunti)

Due eventi A e B sono detti incompatibili (o mutuamente esclusivi) se sono disgiunti, cioè se A ∩ B = ∅ (non possono verificarsi contemporaneamente).

P(A) = probabilità dell'evento A

Ad ogni evento A (misurabile) cerchiamo di associare un numero reale P(A) che rappresenti la probabilità che A ha di verificarsi. P dovrà soddisfare le seguenti condizioni:

1. P(A) ≥ 0 2. P(S) = 1

3. per A 1 , A 2 , A 3 , … mutualmente esclusivi: P(A 1 ∪A ₂ ∪A ₃ ∪ … ) = P(A ₁ ) + P(A 2 ) + P(A 3 ) + …

eventi ugualmente probabili

Spesso si cerca di lavorare con punti campione o eventi elementari che si ritengono ugualmente probabili. Se pensiamo al lotto a numeri, e consideriamo che non ci siano trucchi o difetti, possiamo attribuire ad ogni numero la stessa probabilità di essere pescato. In questi casi possiamo definire la funzione di probabilità facendo il rapporto tra il numero di casi favorevoli e il numero di casi possibili.

Vediamo un esempio semplice: immaginiamo di dover tirare un dado, non truccato, con i numeri da 1 a 6.

Chiamiamo A l'evento che vede uscire un numero pari. Contiamo i casi possibili (6) e i casi in cui il numero che esce è pari (3). Attribuiamo all'evento A la probabilità seguente:

% 2 50 1 6 ) 3

( = = = =

possibili casi

favorevoli

A casi

P

esempio meno semplice: dobbiamo estrarre due palline da un sacchetto che ne contiene 4 nere e 4 bianche.

Chiamiamo B l'evento che vede uscire almeno una pallina nera. Per poter contare facilmente degli eventi equiprobabili, immaginiamo che su ogni pallina ci sia un numero da 1 a 8 e che facciamo attenzione all'ordine di estrazione. Immaginiamo inoltre che le nere abbiano un numero dispari. Contiamo allora i casi possibili (8⋅7=56) e i casi sfavorevoli in cui entrambi i numeri siano pari (4⋅3=12). Se sottraiamo dai casi possibili quelli sfavorevoli otteniamo 44 casi in cui c'è almeno una pallina nera. Ora possiamo attribuire all'evento B la probabilità seguente:

% 6 . 14 78 11 56 ) 44

( = = = ≅

possibili casi

favorevoli

B casi

P

vedremo fra poco altri modi di arrivare a questo risultato

probabilità empirica

La probabilità di un evento può anche essere stimata in modo empirico; se dopo aver ripetuto n volte un

esperimento (n dev'essere molto grande) un evento si è verificato h volte, allora la probabilità di questo evento è

data da h/n. Questa è anche chiamata probabilità empirica di un evento.

Probabilità condizionata

Siano A e B due eventi tali che P(A) > 0. Notiamo con P(B|A) la probabilità di B quando si suppone che A si è verificato. Dal momento che si sa che A si è verificato, esso diviene il nuovo spazio dei campioni in sostituzione di S. E avremo che:

) (

) ) (

|

( P A

B A

A P

B

P = ∩

Eventi indipendenti

Se P(B|A) = P(B) diremo che A e B sono eventi indipendenti. E questo equivale a dire che P(A ∩ B) = P(A)⋅P(B)

Regole di calcolo

Ecco alcune regole che possono servire nel calcolo delle probabilità:

1. P(∅) = 0

2. P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

3. P(A ∩ B) = P(A) ⋅ P(B) se A e B sono eventi indipendenti

4. P(A) = P(A ∩ B) + P(A ∩ B') dove B' è il complementare di B in S

esempio:

Di nuovo valutiamo la probabilità che abbiamo di ottenere almeno una pallina nera quando da un sacchetto che ne contiene 4 nere e 4 bianche ne estraiamo due. Consideriamo 4 eventi a cui sappiamo attribuire una probabilità.

A = 1 ^a nera, 2 ^a nera B = 1 ^a nera, 2 ^a bianca C = 1 ^a bianca, 2 ^a nera D = 1 ^a bianca, 2 ^a bianca

14 3 7 3 2 1 ⋅ =

14 4 7 4 2 1 ⋅ =

14 4 7 4 2 1 ⋅ =

14 3 7 3 2 1 ⋅ =

Questi eventi potrebbero essere gli eventi elementari o punti campione per la nostra doppia estrazione. Comunque questi eventi coprono tutti i casi e non si sovrappongono (sono disgiunti ). Sono dunque una partizione del insieme S. Ora dovrebbe essere facile rispondere alla nostra domanda: P(A ∪ B ∪ C) = P(A) + P(B) + P(C) = 11/14 esercizi

1. Si estrae una carta a caso da un mazzo che ne contiene 52; si descriva lo spazio dei campioni quando (a) i semi non sono presi in considerazione, (b) i semi sono presi in considerazione

2. Con riferimento al problema precedente, sia A l'evento {è uscito un Re} o semplicemente {Re} e B l'evento {è uscito un picche} o semplicemente {picche}. Si descrivano gli eventi (B' = complementare di B)

a) A∪B, b) A∩B, c) A∪B', d) A'∪B', e) A\B, f) A'\B', g) (A∩B)∪(A∩B') 3. Si estragga una carta a caso da un mazzo di 52 carte. Si determini la probabilità che (a) sia un asso, (b) un

fante di quori, (c) un tre di picche o un sei di fiori, (d) un cuori, (e) un seme diverso da cuori, (f) un dieci o un quadri, (g) né un quattro né un picche.

4. Una pallina è estratta in modo casuale da un'urna che ne contiene 6 rosse, 4 bianche e 5 azzurre. Si determini la probabilità che la pallina estratta sia (a) rossa, (b) bianca, (c) azzurra, (d) non rossa, (e) rossa o bianca.

5. Si lanci due volte un dado non truccato. Si determini la probabilità di ottenere 4, 5 o 6 al primo lancio e 1, 2, 3 o 4 al secondo lancio.

6. Trovare la probabilità di non ottenere come somma del lancio di due dadi non truccati né 7 né 11.

7. due carte sono estratte da un mazzo ben mescolato di 52 carte. Si trovi la probabilità che esse siano entrambe assi quando (a) la prima carta è rimessa nel mazzo, (b) non è rimessa nel mazzo

8. Tre palline sono estratte successivamente da un'urna che ne contiene 6 rosse, 4 bianche e 5 azzurre. Si trovi la probabilità che esse siano nell'ordine rossa, bianca e azzurra quando (a) ciascuna pallina è rimessa nell'urna dopo l'estrazione (b) non è rimessa nell'urna

9. Si trovi la probabilità che il 4 si presenti almeno una volta in due lanci di un dado non truccato

10. Un'urna contiene 4 palline bianche e due nere; un'altra urna contiene 3 palline bianche e 5 nere; si estragga una pallina da ciascun'urna e si determini la probabilità che (a) entrambe le palline siano bianche, (b) entrambe siano nere, (c) una sia bianca e una sia nera.

11. L'urna I contiene tre palline rosse e 2 azzurre mentre l'urna II ne contiene 2 rosse e 8 azzurre. Una moneta

non truccata è lanciata per decidere da quale urna estrarre le palline e se si verifica testa si estrae dall'urna I,

in caso contrario dall'urna II. Si determini la probabilità di estrarre un pallina rossa.

Statistica (vedi anche Bergamini modulo M unità 1)

La statistica si occupa di fornire gli strumenti per analizzare grandi quantità di dati. In certi casi i dati ci sono e si tratta di analizzarli. In altri casi si fanno delle congetture sulla base di dati parziali o/e di ipotesi teoriche. Il fine può essere quello di presentare i risultati di un censimento, di mettere in relazione delle frequenze per trovare delle

"leggi" (la sigaretta è considerata cancerogena perchè statisticamente ci sono più persone con il cancro ai polmoni tra i fumatori che tra i non fumatori) o semplicemente di mettere in relazione il comportamento individuale con quello di una moltitudine di individui. Il calcolo delle probabilità interagisce con la statistica in quanto la statistica può fornire dei metodi per stabilire delle probabilità empiriche e, d'altra parte la statistica si serve dei risultati teorici del calcolo delle probabilità.

Per i bisogni della statistica dobbiamo riprendere il calcolo delle probabilità introducendo nuovi concetti.

Variabile casuale

Un punto dello spazio campione non è in genere un numero, però possiamo definire delle funzioni che ad ogni punto dello spazio campione associano un numero. Se ad esempio lanciamo una moneta due volte e

consideriamo uno spazio campione S = {TT; TC; CT; CC}, potremmo definire una funzione X che ad ogni punto campione associa il numero di Teste. Naturalmente X non è l'unica funzione che possiamo definire sullo spazio S.

punto campione TT TC CT CC

X(punto campione) 2 1 1 0

Questa funzione è detta funzione aleatoria o funzione stocastica ma anche variabile stocastica o variabile casuale.

Utilizzeremo d'ora in poi il termine di variabile casuale variabili casuali discrete e continue

L'insieme dei valori che una variabile casuale può assumere può essere discreto o continuo. Nell'esempio dato sopra l'insieme dei valori che può assumere X è {0; 1; 2} , un insieme discreto. Distingueremo allora tra variabile casuale discreta e variabile casuale continua. Per le variabili continue si utilizza normalmente il calcolo integrale.

Distribuzioni di probabilità

Consideriamo ora una funzione f che ad ogni valore x di una variabile casuale X associa un numero che rappresenta la probabilità che ha quel valore di verificarsi. Se riprendiamo l'esempio precedente avremmo:

x 0 1 2

f(x) = P(X=x) 1/4 1/2 1/4

Questa funzione è detta funzione di probabilità o anche distribuzione di probabilità. Rappresentiamo qui sotto graficamente la funzione di probabilità del nostro esempio:

Naturalmente la somma delle probabilità associate a tutti i valori che può assumere X deve valere uno.

X P(X=x)

0 1 2 0.25

0.5

Misure di tendenza centrale

E(X) = µ = Valore medio

Sia X una variabile casuale e f(x) la sua distribuzione di probabilità, si definisce allora il valore medio E di X come la somma di ogni valore che la variabile può assumere moltiplicato per la corrispondente probabilità. In formula:

E(X) = Σ x⋅f(x) (E(X) = ∫ x⋅f(x) se la variabile è continua)

Per l'esempio che ci accompagna avremmo:

E(X) = Σ x⋅f(x) = 1

4 2 1 2 1 1 4

0 ⋅ 1 + ⋅ + ⋅ =

il che significa che in media, su due lanci esce una testa.

Il valore medio, anche detto valore atteso o semplicemente media, ha una grande importanza in probabilità e statistica e si ricorre anche ad un'altra notazione; invece di E(X) si scrive µ x o semplicemente µ se è chiaro a quale variabile casuale ci si riferisce.

Moda, Mediana

Acceniamo ad altre due misure di tendenza centrale.

o La moda di una variabile casuale discreta è quel valore che si realizza più frequentemente o, in altre parole, che ha la più alta probabilità di verificarsi. A volte si possono avere due, tre o più valori che hanno una probabilità di verificarsi relativamente elevata. In questi casi, diciamo che la distribuzione è, rispettivamente, bimodale, trimodale o multimodale. Nel nostro esempio media e moda coincidono ma generalmente non è così.

o La mediana è quel valore di x per il quale abbiamo P(X < x) ≤ 0.5 e P(X > x) ≤ 0.5 . Nel caso di una

distribuzione continua si ha P(X < x) = 0.5 = P(X > x) e la mediana è quel valore che divide i valori di X in due parti equiprobabili (divide la curva di distribuzione di probabilità in due parti di uguali aree).

x y

0 2 4 6 8 10 12 14 16

0 0.05

0.1 0.15

0.2 moda

mediana media

ecco un esempio di distribuzione dove moda, mediana e media hanno valori diversi.

Misure di dispersione

Var(X) = σ ² = Varianza

Consideriamo il quadrato della distanza di un valore x dalla media µ. La varianza ci dice che valore assume, in media, tale quadrato. In formula:

( )

[ ⁻ ] ⁼ _∑ [ ^{( − ) ⋅} ]

= ( )

)

( X E X ² x ² f x

Var µ µ

La varianza è dunque positiva (o nullla) ed è tanto più piccola quanto più i valori si raccolgono attorno alla media.

σ = deviazione standard

La deviazione standard è semplicemente la radice quadrata (aritmetica) della varianza. È notata σ x ο semplicemente σ se è chiaro a quale variabile casuale ci si riferisce.

 ) (X Var _x = σ