1.2.2Disposizioniconripetizione ’ 1.2.1Principibasilari 1.2Calcolocombinatorio

(1)

1.2 Calcolo combinatorio

Ricordiamo dall’Esempio 1.3 che uno spazio di probabilità discreto (W,P) si dice uniforme seW è un insieme finito e si ha P(A) =_|W|^|A|, per ogni A ✓ W. Pertanto, il calcolo della probabilità di un evento in uno spazio uniforme si riduce a contarne il numero di elementi. I problemi di conteggio sono tipicamente non banali e vanno affrontati con attenzione. Lo strumento matematico fondamentale in questo contesto

`e il calcolo combinatorio, che ora descriviamo.

1.2.1 Principi basilari

Dati due insiemi A,B, si dice che A è in corrispondenza biunivoca con B se esiste un’applicazione f : A ! B biunivoca, cioè iniettiva e suriettiva. Chiaramente A è in corrispondenza biunivoca con B se e soltanto se B è in corrispondenza biunivoca con A: si scrive “A e B sono in corrispondenza biunivoca”, che rende palese la simmetria della relazione (si tratta in effetti di una relazione di equivalenza). Dato n 2 N, si dice che un insieme A ha cardinalità n e si scrive |A| = n se A è in corrispondenza biunivoca con l’insieme {1,2,...,n} — ossia, intuitivamente, se “A ha n elementi”. In questo paragrafo considereremo solo insiemi finiti, cioè insiemi che hanno cardinalità n per un opportuno n 2 N.

Per determinare la cardinalit`a di un insieme, la strategia tipica consiste nel ri- condurre il calcolo all’applicazione combinata (talvolta non banale) di alcuni principi o osservazioni basilari. Una prima osservazione, elementare ma molto utile,

`e che se un insieme A `e in corrispondenza biunivoca con un insieme B, allora

|A| = |B|. Un’altra osservazione, anch’essa molto intuitiva, è la seguente: se A,B sono due sottoinsiemi (di uno stesso spazio) disgiunti, cioè tali che A \ B = /0, allora |A [ B| = |A| + |B|. Più in generale, se A1, . . . ,Aksono sottoinsiemi a due a due disgiunti, tali cioè che Ai\ Aj=/0 per i 6= j, allora |^Si=1^k Ai| = Â^ki=1|Ai|. La dimostrazione di queste osservazioni è semplice ed è lasciata per esercizio.

Un principio leggermente meno elementare riguarda la cardinalit`a degli insiemi prodotto. Ricordiamo che, dati due insiemi A,B, il loro prodotto cartesiano A ⇥ B

è definito come l’insieme delle coppie ordinate (a,b), con a 2 A e b 2 B. Vale allora la relazione |A ⇥ B| = |A||B|. Il modo più semplice per convincersi della validità di questa formula consiste nel disporre gli elementi di A ⇥ B in una ta- bella rettangolare, dopo aver numerato gli elementi dei due insiemi. Più precisamente, se A = {a1,a2, . . . ,am}, B = {b1,b2, . . . ,bk}, possiamo elencare gli elementi dell’insieme A ⇥ B nel modo seguente:

(a1,b1) (a1,b2)··· (a1,bk 1) (a1,bk) (a2,b1) (a2,b2)··· (a2,bk 1) (a2,bk)

... ... ... ... ...

(am,b1) (am,b2)··· (am,bk 1) (am,bk) ,

da cui `e chiaro che |A ⇥ B| = m · k = |A| · |B|.

Diamo ora una dimostrazione più formale. Per x 2 A indichiamo con {x} ⇥ B il sottoinsieme di A⇥B costituito dagli elementi che hanno x come prima componente, cioè {x} ⇥ B := {(x,b) : b 2 B}. Possiamo quindi scrivere A ⇥ B = [x2A({x} ⇥ B), e si noti che questa unione è disgiunta, ossia ({x1} ⇥B) \ ({x2} ⇥B) = /0 se x16= x2. Per l’osservazione enunciata sopra si ha dunque |A ⇥ B| = Â_x2A|{x} ⇥ B|. Dato che l’insieme {x} ⇥ B è in corrispondenza biunivoca con B, mediante l’applicazione (x,b) 7! b, segue che |{x} ⇥ B| = |B| e dunque |A ⇥ B| = Â_x2A|B| = |A||B|.

Per induzione si estende facilmente la formula al caso di più di due fattori: dati gli insiemi A1, . . . , Ak, con k 2 N, l’insieme prodotto A1⇥ ··· ⇥ Akè definito come l’insieme delle k-uple (a1, . . . ,ak), con ai2 Ai, e ha cardinalità

|A1⇥ ··· ⇥ Ak| = |A1|···|Ak| =

’

k

i=1|Ai|. (1.19)

Un’estensione di questa formula, elementare ma non banale, conduce a quello che

`e noto come il principio fondamentale del calcolo combinatorio. Prima di vedere di che cosa si tratta, discutiamo qualche applicazione dei principi appena viste.

1.2.2 Disposizioni con ripetizione

Definizione 1.4. Dati k 2 N e un insieme finito A, si dicono disposizioni con ripetizione di k elementi estratti da A le funzioni f : {1,...,k} ! A.

Le disposizioni con ripetizione sono in corrispondenza biunivoca con gli elementi dell’insieme prodotto A^k:= A ⇥ ··· ⇥ A (k volte). In effetti, una corrispondenza naturale `e quella che a (x1, . . . ,xk)2 A^kassocia la funzione f : {1,...,k} ! A definita da f (i) := xi. Per la formula (1.19) sulla cardinalit`a degli insiemi prodotto, si ha che |A^k| = |A|^k=n^k. Abbiamo pertanto il seguente risultato.

Proposizione 1.6. Le disposizioni con ripetizione di k elementi estratti da un insieme di n elementi sono in numero n^k.

Per quanto detto, una disposizione con ripetizione può essere vista come una sequenza ordinata (x1, . . . ,xk)di elementi xi2 A, non necessariamente distinti: si può cioè avere xi=xjper i 6= j. Sottolineiamo che l’ordine in cui compaiono gli elementi

`e importante: per esempio, (a1,a2)e (a2,a1)sono due disposizioni differenti.

Esempio 1.6. (1) I compleanni di un gruppo ordinato di 4 persone costituiscono una disposizione con ripetizione di 4 elementi estratti dall’insieme dei giorni dell’anno, che ha cardinalit`a 366 (contando il 29 febbraio). Sono dunque possibili 366⁴⇡ 1.8 · 10¹⁰sequenze distinte di compleanni.

(2) Per compilare una colonna di una schedina del Totocalcio occorre scegliere, per ciascuna delle 13 partite in esame, tra la vittoria della squadra di casa

(2)

(1), il pareggio (x) o la vittoria della squadra in trasferta (2). Una colonna compilata `e dunque una disposizione con ripetizione di 13 elementi estratti dall’insieme {1,x,2} e di conseguenza ci sono 3¹³⇡ 1.6 · 10⁶modi possibili di compilare una colonna.

(3) Le possibili “parole” (anche prive di significato) costituite da 6 lettere del- l’alfabeto inglese possono essere identificate con le disposizioni con ripetizione di 6 elementi estratti da un insieme — le lettere dell’alfabeto — che ne continene 26: il loro numero è dunque pari a 26⁶⇡ 3.1 · 10⁸. Le parole che effettivamente hanno un significato (per esempio nella lingua inglese) sono naturalmente molte meno: anche includendo i termini tecnici, non si arriva a trecentomila parole. Di conseguenza, la probabilità che digitando una sequenza di sei lettere a caso si ottenga una parola di senso compiuto è certamente (molto) minore di 3 · 10⁵/(3.1 · 10⁸) <10 ³, ossia una probabilità su mille.

Osservazione 1.7. Dati due insiemi A,B, indichiamo con A^Bl’insieme di tutte le funzioni f : B ! A. Se l’insieme B ha cardinalità k 2 N, è facile vedere che A^Bè in corrispondenza biunivoca con A^k(o, equivalentemente, con le disposizioni con ripetizione di k elementi estratti da A): una corrispondenza è per esempio quella che a (x1, . . . ,xk)2 A^kassocia la funzione f 2 A^Bdefinita da f (bi):= xi. Di conseguenza otteniamo la formula |A^B| = |A|^k, cioè |A^B| = |A|^|B|.

1.2.3 Il principio fondamentale

Un esempio molto ricorrente nelle applicazioni `e quello in cui gli elementi di un insieme possano essere determinati attraverso scelte successive.

Esempio 1.7. Sia E l’insieme delle funzioni iniettive da {1,...,k} in un insieme A con |A| = n (si noti che necessariamente k  n). Possiamo determinare ogni funzione f 2 E scegliendo innanzitutto la prima componente f (1) come un elemento qualunque di A, quindi scegliendo la seconda componente f (2) come un elemento qualunque di A \ { f (1)}, e cos`ı via. Abbiamo n esiti possibili per la scelta di f (1), (n 1) esiti possibili per la scelta di f (2), . . . , (n (k 1)) = (n k + 1) esiti possibili per la scelta di f (k). Per analogia con gli insiemi prodotto, dovrebbe essere chiaro che |E| = n · (n 1)···(n k + 1).

Nell’esempio appena descritto, l’insieme degli esiti della scelta i-esima dipende dagli esiti delle scelte precedenti, tuttavia il numero di esiti possibili `e sempre lo stesso, pari a n i + 1. Generalizzando queste considerazioni, giungiamo al principio fondamentale del calcolo combinatorio, che possiamo formulare come segue.

Teorema 1.1 (Principio fondamentale del calcolo combinatorio). Supponiamo che gli elementi di un insieme E possano essere determinati mediante k scelte successive, in cui ogni scelta abbia un numero fissato di esiti possibili: la prima scelta ha n1esiti possibili, la seconda scelta ne ha n2, . . . , la k-esima scelta ne ha nk,

dove n1, . . . ,nk2 N. Supponiamo inoltre che sequenze distinte di esiti delle scelte determinino elementi distinti di E. Allora |E| = n1· n2···nk.

Cos`ı enunciato, questo principio può apparire un po’ vago (per esempio, il con- cetto di “scelta” non è stato definito precisamente). Una riformulazione matematicamente precisa del Teorema 1.1, con la relativa dimostrazione, è data dal Teorema C.1 nell’Appendice C, che comporta tuttavia notazioni piuttosto pesanti e risulta di poco aiuto per l’applicazione del principio a casi concreti.

Nella pratica, si fa tipicamente riferimento all’enunciato del Teorema 1.1. L’idea cruciale è che gli elementi dell’insieme E possono essere messi in corrispondenza biunivoca con le sequenze di esiti delle scelte, che hanno una struttura di spazio prodotto, da cui segue la formula per la cardinalità. La condizione che sequenze distinte di esiti determinino elementi distinti di E serve proprio a garantire che la corrispondenza sia biunivoca: la mancata verifica di questa condizione è la principale fonte di errori nell’applicazione del principio. Qualche esempio chiarirà la situazione.

Esempio 1.8. (a) Un mazzo di carte da poker è costituito da 52 carte, identificate dal seme (cuori ~, quadri }, fiori |, picche ) e dal tipo (un numero da 1 a 10 oppure J, Q, K). Indichiamo con E l’insieme delle carte di numero pari (figure escluse) e di colore rosso (cioè di cuori o di quadri). Ogni elemento di E può essere determinato attraverso due scelte successive: la scelta del seme, che ha 2 esiti possibili (cuori e quadri), e la scelta del tipo, che ne ha 5 (cioè 2,4,6,8,10). Segue dunque che |E| = 2 · 5 = 10.

(b) Dato un mazzo di carte da poker, si chiama full un sottoinsieme di 5 carte costituito dall’unione di un tris (un sottoinsieme di 3 carte dello stesso tipo) e di una coppia (un sottoinsieme di 2 carte dello stesso tipo). Indichiamo con E l’insieme dei possibili full. Sottolineiamo che gli elementi di E sono sottoinsiemi di 5 carte, non disposizioni: in particolare, le carte non sono ordinate.

Gli elementi di E possono essere determinati univocamente attraverso 4 scelte successive: 1) il tipo del tris; 2) il tipo della coppia; 3) i semi delle carte che compaiono nel tris; 4) i semi delle carte che compaiono nella coppia. Per la prima scelta ci sono 13 esiti possibili, per la seconda scelta, qualunque sia l’esito della prima scelta, ci sono 12 esiti possibili (chiaramente i due tipi devono essere differenti, perch´e non esistono cinque carte dello stesso tipo).

Per la terza scelta, occorre scegliere tre semi nell’insieme {cuori, quadri, fiori, picche}: per enumerazione diretta, `e facile vedere che ci sono 4 esiti possibili;

analogamente, per la quarta scelta occorre scegliere due semi e per questo ci sono 6 esiti possibili (ritorneremo nell’Esempio 1.11 sul modo di contare i sottoinsiemi). Applicando il Teorema 1.1 si ottiene dunque che |E| = 13 · 12 · 4 · 6 = 3744.

(c) Dato un mazzo di carte da poker, indichiamo con E l’insieme delle doppie coppie, cio`e i sottoinsiemi di 5 carte costituiti dall’unione di due coppie di tipi diversi, pi`u una quinta carta di tipo diverso dai tipi delle due coppie.

Per determinare |E| si potrebbe essere tentati di procedere analogamente al caso dei full, attraverso sei scelte successive: 1) il tipo della prima coppia; 2)

(3)

il tipo della seconda coppia; 3) il tipo della “quinta carta”; 4) i semi delle carte che compaiono nella prima coppia; 5) i semi delle carte che compaiono nella seconda coppia; 6) il seme della “quinta carta”. Ci sono 13 esiti possibili per la prima scelta, 12 per la seconda scelta, 11 per la terza, 6 per la quarta, 6 per la quinta, 4 per la sesta: si otterrebbe dunque |E| = 13·12·11·6²·4 = 247104.

Tuttavia questo risultato `e errato.

La ragione è che le scelte 1) e 2) sono ambigue, dal momento che non esiste una “prima” e una “seconda” coppia. In effetti, sequenze distinte di esiti delle sei scelte sopra elencate non conducono a elementi distinti di E: ciascun elemento di E, cioè ciascuna doppia coppia, viene infatti selezionata esattamente due volte. Per esempio, la doppia coppia {5~,5},6~,6|,7} viene determinata sia con l’esito “5” della scelta 1) e l’esito “6” della scelta 2), sia viceversa. Per tale ragione, il risultato corretto è |E| = 247104/2 = 123552, cioè la metà di quanto ottenuto in precedenza.

Un modo alternativo di ottenere il risultato corretto `e di riunire le scelte 1) e 2) nell’unica scelta 1bis) “i tipi delle due coppie”, che ha 13 · 12/2 = 78 esiti possibili (anche su questo torneremo nell’Esempio 1.11). Le scelte 1bis), 3), 4), 5) e 6) permettono di applicare correttamente il Teorema 1.1, ottenendo

|E| = 78 · 11 · 6²· 4 = 123552.

1.2.4 Disposizioni semplici e permutazioni

Definizione 1.5. Dati k 2 N e un insieme finito A, si dicono disposizioni semplici (o senza ripetizione) di k elementi estratti da A le funzioni f : {1,...,k} ! A iniettive.

Per quanto visto nell’Esempio 1.7, grazie al principio fondamentale del calcolo combinatorio, il numero di disposizioni semplici di k elementi estratti da un insieme A che ne contiene n `e pari a n(n 1)···(n k+1). Introduciamo per n 2 N il simbolo

“n!”, detto “n fattoriale”, definito come il prodotto degli interi da 1 a n, e poniamo per convenzione 0! := 1:

n! := n(n 1)···1 =

’

ⁿ

i=1i per n 2 N, 0! := 1 . (1.20) Possiamo esprimere riscrivere la formula n(n 1)···(n k + 1) nel modo pi`u compatto n!/(n k)!. Abbiamo dunque mostrato il seguente risultato.

Proposizione 1.7. Le disposizioni semplici di k elementi estratti da un insieme che ne contiene n, dove 1  k  n, sono in numero Dn,k:= n!/(n k)!.

Osservazione 1.8. Per determinare il comportamento asintotico di n! quando n è grande, è di grande utilità la formula di Stirling:

n! ⇠ nⁿe ⁿp

2pn, (1.21)

dove an⇠ bnsignifica che limn!•an/bn=1. Dimostreremo questa formula nella Proposizione 2.1 del capitolo 2.

Osservazione 1.9. In completa analogia con l’Osservazione 1.7, per ogni insieme finito B = {b1, . . . ,bk} con |B| = k il sottoinsieme di A^Bcostituito dalle funzioni iniettive da B in A è in corrispondenza biunivoca con le disposizioni semplici di k elementi estratti da A. La sua cardinalità è pertanto n!/(n k)!.

Un caso speciale molto importante si ha quando B = A. Le funzioni f : A ! A iniettive sono necessariamente suriettive, dunque biunivoche, essendo |A| < •. Esse sono dette permutazioni di A e, per quanto visto, il loro numero è |A|!. È interessante notare che l’insieme delle permutazioni di un insieme fissato A costituisce un gruppo rispetto alla composizione di applicazioni (che è non commutativo se |A| 3).

A meno di corrispondenze biunivoche, non costa niente considerare il caso “speciale” A = {1,...,n}: in questo caso, il gruppo delle permutazioni è indicato con Sned è detto gruppo simmetrico. Munito della probabilità uniforme, lo spazio Sn

ha propriet`a interessanti e per certi versi sorprendenti, alcune delle quali verranno discusse nel paragrafo 2.1.

Esempio 1.9. Supponiamo di mischiare un mazzo di carte da poker. La sequenza ordinata delle carte che ne risulta è una permutazione delle carte del mazzo. Il numero delle possibili sequenze ottenute in questo modo è dunque pari 52! ⇡ 8 · 10⁶⁷. Esempio 1.10 (Paradosso dei compleanni). Si considerino n persone selezionate in modo casuale, nate tutte in un anno non bisestile. Si determini la probabilità pnche almeno due di esse compiano gli anni lo stesso giorno. Quanto grande deve essere grande n affinché pn>1/2?

Numerati i giorni dell’anno e le n persone, lo spazio campionario naturale è dato dalle disposizioni con ripetizione di n elementi dall’insieme dei giorni dell’anno, ossiaW = { f : {1,...,n} ! {1,...,365}}. Abbiamo visto che |W| = 365ⁿ. L’evento di interesse è dato da A = { f 2 W : f non è iniettiva}. Munendo lo spazio W della probabilità uniforme P, si ha dunque

pn=P(A) = 1 P(A^c) =1 |A^c|

|W|, dove, per quanto detto sopra,

|A^c| = |{ f 2 W : f iniettive}| = 365!

(365 n)!=

n 1

’

i=0(365 i).

Si ottiene dunque

pn=1 ’^{n 1}_i=0(365 i)

365ⁿ =1 ^{n 1}

’

i=0

365 i

365 =1 ^{n 1}

’

i=0

✓

1 i

365

◆

. (1.22) Abbiamo ottenuto un’espressione esatta, anche se non del tutto “esplicita”. Con l’ausilio di un calcolatore, si verifica facilmente che pn>¹₂se e solo se n 23. In

(4)

altri termini, in un gruppo di almeno 23 persone c’è una probabilità maggiore del 50% che almeno due persone abbiano lo stesso compleanno, un risultato a prima vista sorprendente. Per un gruppo di 50 persone, la probabilità è maggiore del 97%.

Concludiamo notando che l’espressione (1.22) pu`o essere approssimata in modo esplicito: sfruttando la disuguaglianza 1 x  e ^x, valida per ogni x 2 R, si ha

pn 1 exp

✓ _{n 1}

i=0

Â

i 365

◆

=1 exp

✓ (n 1)n 730

◆ .

Questa espressione `e pi`u grande di¹₂per n > n0=¹₂(1+p

1 + 4 · 730 · log2) ⇡ 22.9, dunque non appena n 23, esattamente come l’espressione esatta.

1.2.5 Combinazioni

Definizione 1.6. Dati k 2 N e un insieme finito A, si dicono combinazioni di k elementi estratti da A i sottoinsiemi di A di cardinalit`a k.

Se una disposizione (semplice o con ripetizione) corrisponde a una sequenza ordinata, una combinazione pu`o essere vista come una collezione non ordinata di elementi dell’insieme A.

Vogliamo ora determinare il numero Cn,kdi combinazioni di k elementi estratti da un insieme A che ne contiene n. Chiaramente Cn,0=1, perché c’è un solo insieme con zero elementi, l’insieme vuoto. Per determinare Cn,kper k 2 {1,...,n}, ricordiamo che ci sono Dn,k=n!/(n k)! disposizioni (cioè sequenze ordinate) di k elementi distinti estratti da A. Dato che nelle combinazioni l’ordine degli elementi non conta, dobbiamo identificare le disposizioni che danno origine alla stessa combinazione, cioè che selezionano lo stesso sottoinsieme di A: dato che ci sono k!

riordinamenti possibili (cio`e permutazioni) di k elementi fissati, si ottiene Cn,k=Dn,k

k! =✓n k

◆

, (1.23)

dove abbiamo introdotto il coefficiente binomiale, definito da

✓n k

◆

:= n!

k!(n k)!, per n 2 N0,k 2 {0,...,n}.

Si noti che la formula Cn,k= ⁿ_k vale anche per k = 0. Abbiamo dunque ottenuto:

Proposizione 1.8. Le combinazioni di k elementi estratti da un insieme che ne contiene n, dove 0  k  n, sono in numero Cn,k= ⁿ_k .

Esempio 1.11. Ritornando brevemente all’Esempio 1.8, il numero di modi di scegliere 3 “semi” tra i quattro possibili {~,},|,} `e pari al numero di combinazioni di 3 elementi estratti da un insieme che ne contiene 4 ed `e dunque dato da ⁴₃ =4

(come avevamo concluso per enumerazione diretta). Analogamente, il numero di modi di scegliere 2 semi `e pari a ⁴₂ =6 e il numero di modi di scegliere due “tipi”

tra i 13 possibili `e pari a ¹³₂ =78.

Una “mano” a Poker `e un sottoinsieme di 5 carte distinte estratte da un mazzo che ne contiene 52. Il numero di possibili mani `e dato dunque da ⁵²₅ =2598960.

Ricordando l’Esempio 1.8, le probabilit`a di fare full oppure doppia coppia valgono rispettivamente 3744/2598960 ⇡ 0.14% e 123552/2598960 ⇡ 4,8%.

Elenchiamo alcune semplici propriet`a dei coefficienti binomiali:

✓n 0

◆

=✓n n

◆

=1, ✓n

k

◆

=✓ n n k

◆

, 8n 2 N0,8k 2 {0,...,n}.

Vale inoltre la relazione

✓n k

◆

=✓n 1 k 1

◆ +✓n 1

k

◆

, 8n 2 N, 8k 2 {0,...,n}, (1.24) come si verifica facilmente.²Ricordiamo infine la formula nota come binomio di Newton:

(a + b)ⁿ =

Â

n k=0

✓n k

◆

a^kb^{n k}, 8n 2 N0,8a,b 2 R, (1.25) che si dimostra per induzione usando (1.24).

Concludiamo con un esempio di grande rilevanza teorica e applicativa, che avremo modo di incontrare nel seguito (si vedano gli Esempi 2.1 e 4.3).

Esempio 1.12. Consideriamo l’esperimento aleatorio che consiste nell’inserire ca- sualmente n oggetti distinti in r cassetti disponibili (ciascun cassetto può contenere un numero qualunque di oggetti). Fissiamo k 2 {0,...,n} e chiediamoci qual è la probabilità che esattamente k oggetti finiscano nel primo cassetto.

Numerati gli oggetti da 1 a n e i cassetti da 1 a r, uno spazio campionario naturale

`e dato dall’insieme

W := f : {1,...,n} ! {1,...,r}

delle disposizioni con ripetizione di n elementi estratti dall’insieme {1,...,r} (e non viceversa!). L’interpretazione è che f 2 W codifica l’esito in cui ogni oggetto i 2 {1,...,n} viene inserito nel cassetto f (i) 2 {1,...,r}. La casualità dell’inserimento induce a munireW della probabilità uniforme P.

L’evento “il primo cassetto contiene k oggetti” corrisponde al sottoinsieme A = { f 2 W : | f ¹(1)| = k} ✓ W delle funzioni che assumono il valore “1” esattamente

2Esiste una dimostrazione “combinatoria” di (1.24). Le combinazioni di k elementi estratti da {1,...,n} sono ⁿk e possono essere divise in due sottoinsiemi disgiunti: quelle che contengono n e quelle che non lo contengono; le prime sono in corrispondenza biunivoca con le combinazioni di (k 1) elementi estratti da {1,...,n 1}, che sono ^{n 1}k 1, mentre le seconde sono in corrispondenza biunivoca con le combinazioni di k elementi estratti da {1,...,n 1}, che sono ^{n 1}k .

(5)

in k elementi distinti del dominio {1,...,n}. Per determinare la cardinalit`a di A, possiamo applicare il principio fondamentale del calcolo combinatorio:

• ci sono ⁿ_k modi di scegliere l’insieme f ¹(1), ossia il sottoinsieme dei k elementi di {1,...,n} che vengono mandati da f in 1;

• una volta fissato l’insieme f ¹(1) — su cui f vale 1 — i valori di f sull’insieme complementare {1,...,n} \ f ¹(1) possono essere scelti arbitrariamente in {2,...,r}, in un numero di modi pari a |{2,...,r}||{1,...,n}\ f ¹(1)|= (r 1)^{n k}, grazie all’Osservazione 1.7 (o, equivalentemente, per il principio fondamentale).

In definitiva |A| = ⁿ_k (r 1)^{n k}e dunque

P(A) = |A|

|W|=

nk (r 1)^{n k}

rⁿ =✓n

k

◆

p^k(1 p)^{n k}, con p =1 r. (1.26) Nel paragrafo 1.3.4 daremo un’interpretazione alternativa a questa espressione.

L’argomento con cui abbiamo derivato la formula (1.23) può essere formalizzato in modo più preciso (e decisamente più tecnico). Cominciamo con un piccolo risultato preparatorio. Siano D,E due insiemi finiti e sia g : D ! E un’applicazione suriettiva. Per ogni y 2 E, introduciamo il sottoinsieme g ¹(y) := {x 2 D : g(x) = y} costituito dagli elementi di D che vengono mandati da g in y.

Supponiamo che valga la seguente proprietà: esiste k 2 N tale che, per ogni y 2 E, si ha |g ¹(y)| = k (cioè per ogni y 2 E esistono esattamente k elementi x 2 D che vengono mandati da g in y). Segue allora che |D| = k|E|. La dimostrazione è semplice: possiamo sempre scrivere E =^Sy2Dg ¹(y) e inoltre l’unione è disgiunta (esercizio). Quindi |E| = Ây2D|g ¹(y)| = Ây2Dk = k |D|.

Fissiamo ora k 2 {1,...,n} e definiamo una applicazione g : Dn,k! Cn,knel modo seguente:

data f 2 Dn,k, definiamo g( f ) := Im( f ), dove Im( f ) indica l’immagine di f (ricordiamo che f

è una funzione iniettiva da {1,...,k} in A). È immediato verificare che g è ben definita, cioè effettivamente g( f ) 2 Cn,kper ogni f 2 Dn,k, e che g è suriettiva. Se mostriamo che |g ¹(B)| = k!, per ogni B 2 Cn,k, si ottiene |Dn,k| = k!|Cn,k| e quindi la formula |Cn,k| = ⁿ_k è dimostrata.

Indichiamo con SBl’insieme delle permutazioni di B, cioè le applicazionip : B ! B biunivoche, e fissiamo un elemento arbitrario f02 g¹(B). È molto facile convincersi che, per ognip 2 SB, si hap f02 g ¹(B): infatti l’applicazionep f0è iniettiva, perché lo sono sia f0siap, e Im(p

f0) =Im( f0) =B, perchép è una permutazione di B. Risulta dunque ben posta l’applicazione H : SB! g ¹(B) definita da H(p) := p f0. Supponiamo che H(p1) =H(p2): per ogni b 2 B, se i 2 {1,...,k} è tale che f0(i) = b (tale i esiste perché Im( f0) =B), otteniamo (p1 f0)(i) = (p2 f0)(i), cioèp1(b) =p2(b); dato che b 2 B è arbitrario, segue che p1=p2, dunque l’applicazione H è iniettiva. Se ora consideriamo un arbitrario f 2 g ¹(B), è facile costruirep 2 SBtale chep f0=f , cioè H(p) = f , quindi l’applicazione H è suriettiva. Avendo mostrato che H è biunivoca, segue che gli insiemi SBe g ¹(B) sono in corrispondenza biunivoca e dunque |g ¹(B)| = |SB| = k! se B 2 Cn,k, che è quanto restava da dimostrare.

1.2.6 Estrazioni di palline da un’urna

Un esempio classico di applicazione del calcolo combinatorio è costituito dai problemi di estrazione di palline da un’urna. Al di là dell’interesse matematico, questo genere di problemi ha grande rilevanza applicativa: modelli basati su urne sono usati ad esempio per descrivere meccanismi di rinforzo in teoria dell’apprendimento. Più

in generale, molti problemi di campionamento da una popolazione possono essere riformulati astrattamente come problemi di estrazione di palline da un’urna.

Ci limiteremo a considerare l’esempio di un’urna contenente N palline di due colori, diciamo M palline rosse e N M verdi (con M  N). Supponiamo di eseguire n estrazioni successive, secondo uno dei seguenti due schemi seguenti:

• Estrazioni con reimmissione. Dopo ogni estrazione, la pallina estratta viene reinserita nell’urna.

• Estrazioni senza reimmissione. Le palline estratte non vengono reinserite. In questo caso dev’essere n  N.

Calcoliamo, per ciascuno dei due schemi, la probabilit`a che esattamente k delle n palline stratte siano rosse.

Estrazioni con reimmissione. Supponiamo di numerare da 1 a M le palline rosse e da (M + 1) a N le palline verdi. L’esito di n estrazioni successive pu`o essere dscritto mediante una disposizione con ripetizione di n elementi presi dall’insieme {1,2,...,N}. Sia dunque W := { f : {1,...,n} ! {1,...,N}} l’insieme di tali disposizioni e sia P la probabilit`a uniforme suW. Denotiamo infine con A l’insieme delle disposizioni contenenti esattamente k palline rosse. Si tratta di calcolare

P(A) = |A|

|W|.

Per determinare |A|, utilizziamo il principio fondamentale. Un elemento di A `e determinato dalle seguenti scelte successive.

• Si scelgono le k posizioni, su n possibili, in cui mettere le palline rosse: per questa scelta ci sono ⁿ_k esiti possibili.

• Si dispongono k palline rosse (prese dalle M presenti nell’urna) nelle posizioni prescelte: ci sono M^ktali disposizioni.

• Si dispongono (n k) palline verdi (prese dalle (N M) presenti nell’urna) nelle rimanenti posizioni: ci sono (N M)^{n k}tali disposizioni.

Si ottiene pertanto

|A| = ✓n k

◆

M^k(N M)^{n k}, e dato che |W| = Nⁿ, segue facilmente che

P(A) = ✓n k

◆

p^k(1 p)^{n k}, dove p :=M

N. (1.27)

Si noti l’analogia con l’espressione (1.26), determinata per un modello diverso.

Questa analogia verr`a reinterpretata pi`u avanti, nel paragrafo 1.3.4.

Estrazioni senza reimmissione. Enumeriamo le palline come nel caso precedente.

Un naturale spazio campionario, in cui la probabilità uniforme esprime la casua- lità dell’estrazione, è quello delle disposizioni senza ripetizione. Tuttavia, poiché

(6)

l’evento “il numero di palline rosse estratte è k” non dipende dall’ordine di estrazione, è forse ancora più naturale scegliere come spazio campionario l’insieme delle combinazioni, e cos`ı faremo.

Sia dunqueW l’insieme dei sottoinsiemi di n elementi dell’insieme {1,2,...,N}, e P la probabilità uniforme su di esso. L’evento di cui vogliamo calcolare la probabilità è

A = {w 2 W : |w \{1,2,...,M}| = k} = {w 2 W : |w \{M +1,...,N}| = n k}.

Chiaramente A = /0 se k > M oppure se (n k) > (N M). Supponiamo dunque che k  M e (n k)  (N M). Ogni elemento di A `e determinato da due scelte successive: occorre scegliere k elementi da {1,2,...,M} e (n k) da {M+1,...,N}.

Di conseguenza possiamo scrivere

|A| = ✓M k

◆✓N M n k

◆ ,

dove usiamo la convenzione secondo cui ⁱ_j =0 se j < 0 o j > i. Ricordando che

|W| = ^N_n , possiamo dunque concludere che

P(A) =

Mk N M Nn k n

. (1.28)

Osservazione 1.10 (Estrazioni da un’urna popolosa). Intuitivamente, se l’urna contiene molte palline di ciascun colore (ossia M 1 e N M 1), non ci dovrebbe essere grande differenza tra i due schemi di estrazioni considerati, dal momento che la rimozione di una pallina modifica in modo trascurabile la composizione dell’urna.

Questo argomento pu`o essere formalizzato matematicamente nel modo seguente.

Sia (MN)_N2Nuna successione di interi positivi tali che

N!•lim MN

N =p 2 (0,1). (1.29)

Se effettuiamo n estrazioni senza reimmissione da un’urna che contiene N palline di cui MNrosse, la probabilità di estrarne esattamente k rosse è data dalla formula (1.28). Mostriamo che il limite per N ! • di tale probabilità, quando i numeri k,n sono fissati, è dato dalla formula (1.27).

Scrivendo ^M_k^N = _k!¹’^{k 1}i=0(MN i) e analogamente per ^{N M}_{n k}^N e ^N_n , con qualche manipolazione algebrica a partire da (1.28) si arriva all’espressione

P(A) =✓n k

◆ _{k 1}

’

i=0

MN i N i

! _{(n k) 1}

’

j=0

N MN j

N k j

!

=✓n k

◆✓ MN

N

◆k(_{k 1}

’

i=0

1 _Mⁱ_N 1 _Nⁱ

)✓

1 MN

N

◆n k(_{(n k) 1}

’

j=0

1 _{N M}^j_N 1 ^{k+ j}_N

) .

Osserviamo che N ! •, MN! • e anche (N MN)! •, grazie a (1.29). Dato che n e k sono fissati, i termini tra parentesi graffe nella relazione precedente tendono a 1 per ` ! •. Poich´e MN/N ! p, segue che

`lim!•P(A) =✓n k

◆

p^k(1 p)^{n k}, (1.30)

che coincide esattamente con l’espressione (1.27), come volevasi dimostrare.

Per questa ragione, quando l’urna contiene molte palline di ciascun colore, il calcolo della probabilità di estrarre k palline rosse in n estrazioni senza reimmissione viene fatto tipicamente usando la formula (1.27), valida per il caso di estrazioni con reimmissione, che è più maneggevole di (1.28) e ne costituisce un’ottima approssimazione (per lo meno se n e k sono molto minori di M e N M).