Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

6 Cap. 1: Calcolo combinatorio

che fornisce un valore approssimato del fattoriale di un numero n per valori abbastanza

1

grandi di n.

Anche per le permutazioni possiamo considerare la possibilità della ripetizione di tutti

gli elementi; in questi casi la formula (2) é ancora applicabile,sostituendo, al posto di k, n.

Esempio 8: Disponendo di bandiere di cinque tipi differenti, quanti messaggi si possono

formare con queste bandiere, se possiamo avere anche la ripetizione delle stesse?

Abbiamo:

55

D'(5,5) = = 3125.

Supponiamo ora di voler calcolare il numero delle permutazioni delle lettere contenute

nella parola LOLLO, parola in cui la lettera L é ripetuta 3 volte e la lettera O due volte. In casi

come questi, si parla di permutazioni con ripetizioni (nel nostro esempio, di 5 elementi di cui

uno presente 3 volte ed uno presente due volte). Per calcolare il numero di queste permutazioni

supponiamo, in un primo momento, che le lettere ripetute non siano uguali ma diverse e le

distingueremo con un indice (provvisorio!). Così, delle seguenti permutazioni:

L1L2L3O1O2 L1L2L3O2O1

L1L3L2O1O2 L1L3L2O2O1

L2L1L3O1O2 L2L1L3O2O1

L2L3L1O1O2 L2L3L1O2O1

L3L1L2O1O2 L3L1L2O2O1

L3L2L1O1O2 L3L2L1O2O1

(12 in tutto: 6x2 = 3!x2!, ottenute dalla permutazione delle tre L e delle due O) dobbiamo

prendere in considerazione solo una, in quanto gli indici sono solo fittizi. Quindi possiamo

calcolare le permutazioni delle lettere della parola LOLLO, calcolando prima le permutazioni

di tutte e cinque le lettere supposte diverse e dividendo il risultato per 12=3!x2!:

5! 120

P(5,3,2) = = = 10.

3!2! 12

Possiamo generalizzare il risultato e considerare il caso in cui vogliamo calcolare il nu-

mero delle permutazioni con ripetizione di n elementi, fra cui k

1, k

2, ..., k sono uguali fra loro

r

   

(ma tali che ) e scrivere che tale numero é uguale a:

k k ... k n

1 2 r

1 L'applicazione della formula di Stirling comporta la conoscenza delle funzioni esponenziali e logaritmiche. Gli

studenti che non conoscono ancora queste funzioni possono applicarla successivamente per calcolare, ad esempio,

un valore approssimato di 150! e 2500!. 7

R. SANTORO: Elementi di calcolo delle probabilità n

!

P ( n , k , k ,..., k ) = (4)

1 2 r k !

k !... k !

1 2 r

Esempio 9 Vogliamo fare una ripartizione di 15 studenti in 3 classi: 5 nella classe A, 4 nella

classe B e 6 nella classe C. In quanti modi possiamo fare questa ripartizione?

Possiamo risolvere il problema proposto supponendo che la ripartizione sia già

fatta e che i 5 studenti della classe A siano paragonabili a cinque A ripetute, i 4

studenti della classe B siano paragonabili a quattro B ripetute ed infine che i 6

studenti della classe C siano paragonabili a 6 C ripetute. Quindi il numero

cercato é: 15

!

 

P(

15

;

5

,

4 ,

6

) 630630

5

! 4 ! 6!

1.4 Combinazioni semplici

Supponiamo che una classe di 15 alunni debba mandare una delegazione di tre studenti

ad un certo congresso. In quanti modi diversi é possibile scegliere gli studenti della

delegazione? Il problema somiglia molto ad un problema di disposizioni semplici, solo che, in

questo caso, l'ordine con cui vengono scelti i 3 studenti non ha alcuna importanza. Allora se A,

B e C sono tre studenti scelti, le permutazioni semplici dei tre studenti conducono sempre alla

stessa scelta. Dunque dobbiamo calcolare le disposizioni semplici di 15 elementi presi 3 alla

volta e dividere il risultato per 3!; avremo quindi che il numero richiesto é:

 

15 14 13 = 455

3

!

In casi come questi, in cui due raggruppamenti sono diversi soltanto se hanno almeno

un elemento diverso, si parla di combinazioni semplici di n elementi presi k alla volta: il cui

kn

numero indicheremo con C(n,k) o con .

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


PAGINE

16

PESO

241.45 KB

AUTORE

Exxodus

PUBBLICATO

+1 anno fa


DETTAGLI
Esame: Statistica
Corso di laurea: Corso di laurea magistrale in scienze statistiche ed economiche
SSD:
Docente: Non --
A.A.: 2008-2009

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Exxodus di informazioni apprese con la frequenza delle lezioni di Statistica e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Non --.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea magistrale in scienze statistiche ed economiche

Demografia - Appunti
Appunto