Laboratorio virtuale > Calcolo combinatorio > [1] 2 3 4 5
Se una variabile casuale X di un esperimento è distribuita uniformemente su un sottinsieme finito S, allora la distribuzione di probabilità di X è proporzionale alla misura di conteggio:
P(X A) = #(A) / #(S) per A S.
Variabili casuali di questo tipo si presentano di frequente in diversi tipi di esperimento, in particolare quelli che possono essere interpretati come campionamento da un insieme finito. L'insieme S è di solito molto grande, sono quindi essenziali metodi di conteggio efficienti. Il primo problema combinatorio è attribuito al matematico greco Xenocrate.
In molti casi, un insieme di oggetti può essere contato stabilendo una corrispondenza biunivoca tra l'insieme dato e un altro insieme. Ovviamente, i due insiemi hanno lo stesso numero di elementi, ma per qualche ragione il secondo può essere più semplice da contare.
La regola additiva del calcolo combinatorio è semplicemente l'assioma di additività della misura di conteggio. Se A1, A2, ..., An sono sottinsiemi disgiunti di un insieme finito S allora
#(A1 A2 ··· An) = #(A1) + #(A2) + ··· + #(An)
Ricorda inoltre che le regole della probabilità hanno i loro analoghi per la misura di conteggio. Le più importanti sono riportate nei seguenti esercizi:
1. Prova che #(Ac) = #(S) - #(A)
2. Prova che #(B Ac) = #(B) - #(A B).
3. Prova che se A B allora #(B Ac) = #(B) - #(A).
4. Prova che #(A B) = #(A) + #(B) - #(A B).
5. Prova che
#(A B C) = #(A) + #(B) + #(C) - #(A B) - #(A C) - #(B C) + #(A B C).
Gli esercizi 11 e 12 possono essere generalizzati all'unione di n eventi Ai, i = 1, 2, ...n; la generalizzazione è detta formula di inclusione-esclusione. Per semplificare la notazione, sia N l'insieme di indici: I = {1, 2, ..., n} e definiamo
nJ = # [j in J Aj] for J N,
mk = {J: #(J) = k} nJ per k N.
6. Prova che # [i = 1, ..., n Ai] = k = 1, ..., n (-1)k - 1 mk.
Le disuguaglianze di Bonferroni affermano che se la sommatoria al termine di destra è troncata dopo k termini (k < n), allora la sommatoria troncata è un limite superiore per la cardinalità dell'unione se k è dispari (cosicché l'ultimo termine ha segno positivo) e inferiore per la cardinalità dell'unione se k è pari (cosicché l'ultimo ha segno negativo).
La regola del prodotto del calcolo combinatorio è basata sulla formulazione di una procedura (o algoritmo) che genera gli oggetti che vengono contati. Specificamente, supponiamo che la procedura consista di k passi, eseguiti in sequenza, e che per ogni passo j possa essere eseguito in nj modi, indipendentemente dalle scelte fatte ai passi precedenti. Allora, il numero di modi in cui si può eseguire l'intero algoritmo (e quindi il numero di oggetti) è
n1 n2 ··· nk.
Il modo per applicare correttamente la regola del prodotto a un problema di conteggio è formulare in maniera precisa un algoritmo che genera gli oggetti che si devono contare, cosicché ogni oggetto sia generato una e una sola volta.
I primi due esercizi qui sotto riportano formulazioni equivalenti del principio del prodotto.
7. Supponi che S sia un insieme di successioni di lunghezza k, e che si indichino gli elementi di S con
(x1, x2, ..., xk)
Supponi che, per ogni j, xj abbia nj differenti valori, indipendentemente dai valori delle coordinate precedenti. Prova che la cardinalità di A è
n1 n2 ··· nk.
8. Supponi che T sia un albero ordinato con profondità k e che ogni vertice di livello i - 1 abbia ni figli per i = 1, 2, ..., k. Prova che il numero di vertici a livello k è
n1 n2 ··· nk.
9. Un numero identificativo è formato da due lettere (maiuscole) seguite da cinque numeri (0-9).
10. Supponi che un PIN (Personal Identification Number) sia una parola formata da quattro simboli in cui ciascun simbolo può essere un numero o una lettera (maiuscola).
11. Nel gioco da tavola Cluedo, il signor Boddy è stato assassinato. Ci sono sei sospettati, sei possibili rami del delitto e nove possibili stanze del delitto.
12. Supponi che Si sia un insieme con ni elementi per i = 1, 2, ..., k. Prova che
#(S1 × S2 × ··· × Sn ) = n1 n2 ··· nk.
In particolare, se Si è lo spazio campionario dell'esperimento Ei, allora questo prodotto dà il numero di esiti dell'esperimento composto consistente nell'eseguire E1, ..., Ek in sequenza.
13. Un esperimento consiste nel lanciare un dado bilanciato, estrarre una carta da un mazzo standard e lanciare una moneta equilibrata.
14. Mostra che, se S è un insieme di m elementi, allora Sn ha mn elementi.
In particolare, se un esperimento semplice ha m esiti, allora l'esperimento composto che consiste di n replicazioni dell'esperimento semplice ha mn esiti.
15. Si lancia 5 volte un dado bilanciato e si registra la sequenza di punteggi.
16. Prova che il numero di campioni ordinati di dimensione n che può essere estratto con reinserimento da una popolazione di m unità è mn.
17. Supponi che 10 persone siano selezionate a caso e se ne registrino i compleanni.
18. Mostra che il numero di funzioni da un insieme A di n elementi in un insieme B di m elementi è mn.
Gli elementi di {0,1}n si dicono a volte stringhe di bit di lunghezza n. L'esito dell'esperimento formato da n prove Bernoulliane è una stringa di bit di lunghezza n.
19. Prova che il numero di stringhe di bit di lunghezza n è 2n.
20. Si lancia 10 volte una moneta bilanciata.
21. Una ghirlanda di luci ha 20 lampadine, ciascuna delle quali può essere guasta o funzionante. Quante possibili configurazioni ci sono?
22. L'esperimento dado-moneta consiste nel lanciare un dado e poi lanciare una moneta il numero di volte indicato dal dado. Si registra la sequenza di risultati delle monete.
23. Replica l'esperimento dado-moneta 1000 volte, aggiornando ogni 10. Confronta la probabilità empirica che tutte le monete siano testa con la probabilità vera trovata nell'esercizio precedente.
La tavola di Galton, che prende nome da Francis Galton, è una matrice triangolare di chiodi (Galton la chiamò quincunx). Le righe sono numerate, da cima a fondo, con 0, 1, .... La riga k ha k + 1 chiodi etichettati, da sinistra a destra, con 0, 1, ..., i. Pertanto, un chiodo può essere identificato unicamente da una coppia ordinata (i, j) dove i è il numero di riga j è il numero del chiodo della riga.
Si lascia cadere una pallina sul chiodo iniziale (0, 0) della tavola di Galton. In generale, quando la pallina colpisce il chiodo (i, j), può finire a sinistra, sul chiodo (i + 1, j) o a destra, sul chiodo (i + 1, j + 1). La sequenza di chiodi che la pallina colpisce è detta sentiero.
24. Mostra che esiste una corrispondenza biunivoca tra ciascuna coppia delle seguenti tre collezioni:
Segue quindi, dall'esercizio precedente, che ciascuna delle seguenti collezioni ha 2n elementi. In particolare, un esperimento con n esiti ha 2n eventi.
25. Nel gioco della tavola di Galton, muovi la pallina da (0,0) a (10,6) seguendo un sentiero a tua scelta. Osserva la corrispondente stringa di bit e sottinsieme.
26. Nel gioco della tavola di Galton, genera la stringa di bit 011100101. Osserva il corrispondente sentiero e sottinsieme.
27. Nel gioco della tavola di Galton, genera il sottinsieme {2, 4, 5, 9, 12}. Osserva la corrispoendente stringa di bit e sentiero.
28. Nel gioco della tavola di Galton, genera tutti i sentieri tra (0, 0) e (4, 2). Quanti sentieri ci sono?
29. Supponi che A1, A2, ..., Ak siano eventi di un esperimento casuale. Prova che esistono 2^(2k) eventi differenti (in genere) che possono essere costruiti a partire dai k eventi dati, utilizzando le operazioni di unione, intersezione e complementazione. I seguenti passi mostrano come:
30. Nell'applet diagramma di Venn, osserva il diagramma di ciascuno dei 16 eventiche possono essere costruiti a partire da A e B.
31. Supponi che S sia un insieme formato da n elementi e che A sia un sottinsieme di S con k elementi. Se si seleziona casualmente un sottinsieme di S, trova la probabilità che contenga A.
Le applicazioni più semplici del principio del prodotto sono le permutazioni e le combinazioni. È interessante anche notare che il principio del prodotto è la misura di conteggio analoga alla regola del prodotto per la probabilità condizionata. I metodi di calcolo combinatorio ricoprono un ruolo fondamentale nel capitolo sui modelli di campionamento finito.