Calcolo combinatorio e probabilità

C

Da quanto visto sopra abbiamo facilmente che:

D

( n

, k )

C ( n

, k ) = .

k

!

Dunque, combinando la formula precedente con la (1'), avremo:

n

!

C ( n , k ) = (5)

k

!( n - k )!

Esempio 10 Gioco del Lotto. Anche questo é un gioco molto popolare in Italia. In un urna ci

sono 90 palline numerate da 1 a 90. Vengono estratte, una dopo l'altra e senza

reimbussolamento, 5 palline. Si vince se si riesce ad indovinare, in una giocata

precedente l'estrazione, una coppia di numeri (ambo), una terna di numeri

8 Cap. 1: Calcolo combinatorio

(terno), una quaterna di numeri (quaterna), i 5 numeri (cinquina). Calcolare il

numero di ambi, terni, quaterne, cinquine possibili.

In tutti i casi si tratta di combinazioni semplici di 90 elementi presi 2, 3, 4 o 5

alla volta, rispettivamente. Quindi possiamo scrivere:

90! 

90

n( ambi ) = C = = 45 89 = 4005.

2 2!88!  

90! 90 89 88

90

n( terni ) = C = = = 117480.

3 3!87! 6   

90! 90 89 88 87

90

n( quaterne

) = C = = = 2555190.

4 4!86! 24

   

90! 90 89 88 87 86

590

n( quintine

) = C = = = 43949268.

5!85! 120

Come si vede dal calcolo precedente, se da una parte é relativamente semplice

realizzare un ambo, diventa sempre più difficile realizzare un terno, una

quaterna, una quintina (quasi 44 milioni di quintine possibili!).

Sarebbe interessante anche esaminare come lo Stato, gestore del gioco,

ricompensa (si fa per dire...) le eventuali vincite.

Esempio 11 Nella figura sottostante é rappresentato un reticolato formato da 36 quadrati;

ciascun vertice dei quadrati viene individuato da una coppia di numeri (che

potrebbero essere le coordinate cartesiane dei vertici stessi), da 0 a 9 in

orizzontale e da 0 a 4 in verticale. In quanti modi diversi si può andare,

seguendo i lati dei quadrati, dal punto (0,0) al punto (9,4)?

(0,4) (9,4)

(0,0) (9,0)

Possiamo rappresentare i diversi spostamenti usando il simbolo d per indicare

uno spostamento orizzontale verso destra, il simbolo a per indicare uno

spostamento verticale verso l'alto. Allora uno dei possibili itinerari

(rappresentato in figura) é:

dddaadddaddad. 9

R. SANTORO: Elementi di calcolo delle probabilità

Evidentemente bisogna percorrere, in orizzontale o in verticale, tredici cammini

unitari e possiamo scegliere 9 o 4 di questi cammini come é immediato rendersi

conto. Quindi avremo che il numero dei cammini richiesto é dato da:

  

13! 13 12 11 10

9+4 13

C = C = = = 2860,

9 9 9!3! 6

oppure da: 13!

9+4 13

C = C = = 2860.

4 4 4!9!

Dall'esempio precedente abbiamo visto che:

 

913 13 13 .

C C C



13 9 4

Il risultato dell'esempio precedente é del tutto generale e può essere dimostrato in modo

diretto a partire dalla (5). Possiamo allora concludere che:



kn n

C C (6)



n k

.

1.5 Coefficienti binomiali e binomio di Newton

Tenendo conto delle convenzioni fatte sul fattoriale di un numero, possiamo facilmente

verificare che, fissato n e facendo variare k da k = 0 fino a k = n, abbiamo la seguente tabella

kn

dei valori di per i primi 8 valori di n:

C kn

C

n\k 0 1 2 3 4 5 6 7 8

0 1

1 1 1

2 1 2 1

3 1 3 3 1

4 1 4 6 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1

7 1 7 21 35 35 21 7 1

8 1 8 28 56 70 56 28 8 1

La tabella precedente ci suggerisce alcune osservazioni:

 

n nn

a) Per ogni n: .

C C 1

0 

 

kn kn kn 11

C C C

b) Per ogni n: ; questa circostanza é stata messa in evidenza nella tabella,



1

dove si può notare, ad esempio, che:

C(5,1)+C(5,2) = 5 + 10 = 15 = C(5+1,1+1) = C(6,2)

C(7,4)+C(7,5) = 35 + 21 = 56 = C(7+1,4+1) = C(8,5).

10 Cap. 1: Calcolo combinatorio

c) Se guardiamo i numeri di ogni riga, ci viene subito da pensare ai coefficienti numerici

n

dello sviluppo di (x + y) (potenza n-esima di un binomio). Per esempio, lo sviluppo:

4 4 3 2 2 3 4

(x + y) = x + 4x y + 6x y + 4xy + y

ha i coefficienti numerici 1, 4, 6, 4 e 1, corrispondenti ai valori forniti dalla tabella

precedente per n = 4. Per questo motivo i numeri forniti dalla tabella precedente si

chiamano anche coefficienti binomiali e si indicano con

 

n

 

 

k

da leggere 'n su k' (senza alcuna relazione con la divisione!).

E' evidente che utilizzando il nuovo simbolo per i coefficienti binomiali, risulta:

 

n

  

kn .

C  

k

Utilizzando il nuovo simbolo, la potenza n-sima di un binomio si può esprimere

mediante la formula:  

k = n n

  

n n - k k (7)

( x + y ) = x y

 

k

k = 0

formula che che usa anche un nuovo simbolo (, sigma maiuscolo, simbolo di sommatoria in

matematica, da leggere sommatoria per k uguale a 0 fino a k uguale a n di ...).

La (7) si chiama anche formula del binomio di Newton e la tabella precedente prende

il nome di triangolo di Tartaglia (i francesi la chiamano triangolo di Pascal).

 

 6

Esempio 12: Calcoliamo lo sviluppo di .

x 2 y

Utilizzando i coefficienti forniti dal triangolo di Tartaglia o la formula di

Newton abbiamo:

 

 6

x 2 y =

       

6 6 6 6

       

• • • •

6 0 5 1 4 2 3 3

= +

x (-2 y ) + x (-2 y ) + x (-2 y ) + x (-2 y )

       

0 1 2 3

     

6 6 6

     

• • •

2 4 1 5 0 6 =

+ x (-2 y ) + x (-2 y ) + x (-2 y )

     

4 5 6

     

6 5 4 2 3 3 2 4 5 6

= .

x 12 x y 60 x y 160 x y 230 x y 192 xy 64 y

1.6 Diagrammi ad albero

A volte diventa difficile classificare un determinato problema combinatorio e quindi

applicare la formula delle disposizioni o quella delle combinazioni, semplici o ripetute. In

alcuni di questi casi (ma anche in altri di facile classificazione) risulta utile schematizzare il

11

R. SANTORO: Elementi di calcolo delle probabilità

problema con un diagramma ad albero (così chiamato a causa della sua struttura ramificata) per

enumerare tutti i possibili esiti di una serie di esperimenti, ciascuno dei quali può avere solo un

numero finito di esiti. Altre volte é anche necessario conoscere, oltre al numero, anche la lista

completa di tutti gli esiti possibili: pure in questi casi, un diagramma ad albero é di grande

aiuto.

Esempio 13 Lanciamo una moneta 3 volte. Quanti risultati diversi (successioni di testa e

croce) possiamo avere?

Osserviamo lo schema seguente, dove possiamo notare che per ognuno dei lanci

sono rappresentati i due risultati possibili: T (testa) e C (croce).

C

T

T C T C

T C T C T C T C

TTT TTC TCT TCC CTT CTC CCT CCC

Dallo schema precedente non solo abbiamo la possibilità di contare tutti i

possibili esiti, 8, del nostro esperimento ripetuto tre volte, ma abbiamo anche

l'elenco completo degli esiti possibili, che sono quelli scritti alla fine di ciascun

ramo.

Esempio 14 Lanciamo due dadi per studiare la somma dei risultati delle due facce 'vincenti'.

Vogliamo calcolare il numero delle configurazioni che generano un determinato

risultato della somma, dal 2 al 12.

Primo dado 1 2 3 4 5 6

Secondo 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

dado

Conf.razioni: 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6

1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6

Dallo schema precedente (dove le configurazioni sono da leggere in verticale)

deduciamo facilmente i seguenti risultati per ciascuna somma possibile:

Somma 2 3 4 5 6 7 8 9 10 11 12

N. configurazioni 1 2 3 4 5 6 5 4 3 2 1

12 Cap. 1: Calcolo combinatorio

1.7 Problema risolto e sua generalizzazione

Supponiamo di voler disporre 3 oggetti in tre cassetti diversi. Vogliamo calcolare il

numero dei modi differenti in cui l’operazione puó essere effettuata.

La prima soluzione che viene in mente è quella di shematizzare tutte le possibili confi-

gurazioni e quindi contarle, come nello schema seguente (dove gli oggetti sono rappresentati da

piccole clessidre):



1 Dallo schema il conto è facile: ci sono 10

modi diversi di sistemare i tre oggetti nei tre

cassetti.

 

2 Peró la soluzione trovata è molto artigianale

e poco razionale e non siamo soddisfatti. In

 

3 pratica siamo nella stessa situazione del

1

paragrafo : supponendo che i numeri siano

 

4 molto piú grandi, una soluzione del genere

(mediante elencazione completa di tutti i casi

 

5 possibili) sarebbe semplicemente impensabi-

le.

  

6 Razionalmente possiamo pensare agli oggetti





7 e alle separazioni dei cassetti ( ) come ad

uniche entità (articoli). Se trascuriamo la

  prima e l’ultima barretta verticale (poste

8 sempre nelle stesse posizioni), ci sono da

  sistemare tre oggetti e due barrette verticali

9 (5 articoli). Ad esempio, per la configurazio-

.

 ne , abbiamo:

10 3

Dunque, il numero delle possibili configurazioni è uguale a:

 

5

  = 10 (numero dei modi di scegliere due barrette fra 5 articoli), oppure

 

2

 

5

  =10 (numero dei modi di scegliere tre oggetti fra 5 articoli).

 

3

Il risultato raggiunto puó essere generalizzato al caso di n oggetti da sistemare in k

cassetti diversi: abbiamo k + 1 barrette verticali per formare k cassetti, ma due di queste sono

sempre alle due estremità; allora in tutto abbiamo k + 1 - 2 = k - 1 barrette verticali e n oggetti.

Dunque il numero delle configurazioni possibili è uguale al numero di combinazioni di n + k - 1

elementi presi k - 1 alla volta, oppure al numero di combinazioni di n + k - 1 elementi presi n

alla volta:    

   

n k 1 n k 1



    .



   

k 1 n 13

R. SANTORO: Elementi di calcolo delle probabilità

1.8 Esercizi

1. In quanti modi 8 persone possono sedersi su una panchina che ha 5 posti?

2. Una comitiva di 7 uomini e 6 donne devono sedersi in fila in modo che gli uomini ab-

biano solo posti dispari. Quante sistemazioni diverse esistono?

3. Quanti numeri di quattro cifre possono essere formati con le 10 cifre 0,1,2,...9 se:

a) si ammettono delle ripetizioni;

b) le