Laboratorio virtuale > Calcolo combinatorio > [1] 2 3 4 5

1. Principi fondamentali


Distribuzioni uniformi discrete

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 in A) = #(A) / #(S) per A sottinsieme 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.

Corrispondenza biunivoca

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

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 unione A2 unione ··· unione 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:

Esercizio teorico 1. Prova che #(Ac) = #(S) - #(A)

Esercizio teorico 2. Prova che #(B intersezione Ac) = #(B) - #(A intersezione B).

Esercizio teorico 3. Prova che se A sottinsieme B allora #(B intersezione Ac) = #(B) - #(A).

La formula di inclusione-esclusione

Esercizio teorico 4. Prova che #(A unione B) = #(A) + #(B) - #(A intersezione B).

Esercizio teorico 5. Prova che

#(A unione B unione C) = #(A) + #(B) + #(C) - #(A intersezione B) - #(A intersezione C) - #(B intersezione C) + #(A intersezione B intersezione 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 = # [intersezionej in J Aj] for J sottinsieme N,

mk = sommatoria{J: #(J) = k} nJ per k in N.

Esercizio teorico 6. Prova che # [unionei = 1, ..., n Ai] = sommatoriak = 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

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.

Esercizio teorico 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.

Esercizio teorico 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.

Esercizio teorico 9. Un numero identificativo è formato da due lettere (maiuscole) seguite da cinque numeri (0-9).

  1. Quanti diversi numeri identificativi esistono?
  2. Se si sceglie a caso un numero identificativo, trova la probabilità che i numeri siano tutti minori di 5.

Esercizio teorico 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).

  1. Quanti PIN esistono?
  2. Se si sceglie a caso un PIN, trova la probabilità che tutti i simboli siano lettere.

Esercizio teorico 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. 

  1. Il gioco include una carta per ogni sospettato, arma e stanza. Quante carte ci sono?
  2. L'esito del gioco è una sequenza formata da un sospettato, un'arma e una stanza (per esempio, il Colonello Mustard col coltello nella stanza del biliardo). Quanti esiti ci sono?
  3. Una volta che le tre carte che costituiscono la soluzione sono state estratte, le carte restanti sono distribuite tra i giocatori. Supponi di ricevere 5 carte: quale mano è la migliore al fine di trovare la soluzione?

Insiemi prodotto

Esercizio teorico 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.

Esercizio teorico 13. Un esperimento consiste nel lanciare un dado bilanciato, estrarre una carta da un mazzo standard e lanciare una moneta equilibrata.

  1. Quanti esiti ci sono?
  2. Trova la probabilità che il punteggio del dado sia pari, la carta sia di cuori e la moneta sia testa.

Esercizio teorico 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.

Esercizio teorico 15. Si lancia 5 volte un dado bilanciato e si registra la sequenza di punteggi.

  1. Quanti esiti ci sono?
  2. Trova la probabilità che il primo e l'ultimo lancio siano 6.

Esercizio teorico 16. Prova che il numero di campioni ordinati di dimensione n che può essere estratto con reinserimento da una popolazione di m unità è mn.

Esercizio teorico 17. Supponi che 10 persone siano selezionate a caso e se ne registrino i compleanni.

  1. Quanti esiti ci sono?
  2. Trova la probabilità che tutte e 10 le persone siano nate di maggio.

Esercizio teorico 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.

Esercizio teorico 19. Prova che il numero di stringhe di bit di lunghezza n è 2n.

Esercizio teorico 20. Si lancia 10 volte una moneta bilanciata.

  1. Quanti esiti ci sono?
  2. Trova la probabilità che i primi tre lanci diano testa.

Esercizio teorico 21. Una ghirlanda di luci ha 20 lampadine, ciascuna delle quali può essere guasta o funzionante. Quante possibili configurazioni ci sono?

Esercizio teorico 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.

  1. Quanti esiti ci sono?
  2. Trova la probabilità che tutte le monete risultino testa.

Simulazione 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

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.

Esercizio teorico 24. Mostra che esiste una corrispondenza biunivoca tra ciascuna coppia delle seguenti tre collezioni:

  1. Stringhe di bit di lunghezza n
  2. Sentieri nella tavola di Galton da (0, 0) fino a un chiodo della riga n.
  3. Sottinsiemi di un insieme con n elementi.

Segue quindi, dall'esercizio precedente, che ciascuna delle seguenti collezioni ha 2n elementi. In particolare, un esperimento con n esiti ha 2n eventi.

Simulazione 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.

Simulazione 26. Nel gioco della tavola di Galton, genera la stringa di bit 011100101. Osserva il corrispondente sentiero e sottinsieme.

Simulazione 27. Nel gioco della tavola di Galton, genera il sottinsieme {2, 4, 5, 9, 12}. Osserva la corrispoendente stringa di bit e sentiero.

Simulazione 28. Nel gioco della tavola di Galton, genera tutti i sentieri tra (0, 0) e (4, 2). Quanti sentieri ci sono?

Esercizio teorico 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:

  1. Mostra che esistono 2k eventi a due a due disgiunti della forma B1 B2 ··· Bk dove Bi è o Ai o Aic per ogni i.
  2. Spiega perché ogni evento che può essere costruito a partire da A1, A2, ..., Ak è l'unione di qualcuno (forse tutti, forse nessuno) degli eventi in (a).

Simulazione 30. Nell'applet diagramma di Venn, osserva il diagramma di ciascuno dei 16 eventiche possono essere costruiti a partire da A e B.

Esercizio teorico 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.

Argomenti correlati

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.