Probabilità/Calcolo combinatorio: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 15:
'''La Regola Fondamentale di Conteggio''' : Se da una serie di scelte o prove T1, T2, T3, . . . , Tk, potrebbero derivare, rispettivamente, n1, n2, n3, . . . ,nk possibili risultati, l'intera serie di k scelte o prove ha n1 × n2 × n3 × . . . × nk possibili risultati. (I numeri n1, n2, n3, . . . , nk non possono dipendere dal risultato che si verifica realmente).
Dalla Regola Fondamentale di Conteggio, il numero totale delle possibili sequenze di scelte è 5 × 4 × 3 × 2 × 1 = 120 sequenze. Ogni sequenza è chiamata permutazione di cinque elementi. Una permutazione di elementi è un ordinamento degli elementi. Più generalmente dalla Regola Fondamentale di Conteggio, nell'ordinamento di n cose, ci sono n scelte per la prima, (n-1) scelte per la seconda, etc., quindi il numero totale dei modi di ordinamento di un totale di n cose è n × (n-1) × (n-2) × . . . × 1. Questo prodotto, n×(n-1)×(n-2)× . . . ×1, è anche scritto n!, che si legge "n fattoriale." Per convenzione, 0! = 1.
Il principio di conteggio è la regola guida anche per il calcolo del numero di elementi di un prodotto cartesiano.
Riga 25:
Il numero degli elementi nel prodotto cartesiano S x T è uguale ad mn. Notiamo che il numero totale di risultati non dipendono dall'ordine nel quale gli esperimenti sono realizzati.
[[File:Countingprinciple.png|senza_cornice|centro | Figura 9]]
'''Figura 9'''
Riga 39:
Se noi indichiamo la cardinalità di <math>S_p</math> by <math>n_p = | S_p |</math>, allora il numero di r-tuple in ordine distinto delle forme <math>(s_1, s_2, \ldots, s_r)</math> è <math>n = n_1 n_2 \cdots n_r</math>.
'''Esempio - Campionamento con sostituzione e ordinamento''': un'urna contiene n palline numerate da 1 a n. Una pallina viene estratta dall'urna e il suo numero viene registrato su un elenco ordinato. La pallina viene poi reinserita nell'urna. Questa procedura è ripetuta k volte. Noi desideriamo calcolare il numero di possibili sequenze che possono risultare da questo esperimento. Ci sono k estrazioni ed n possibilità per ogni estrazione. Usando il principio di conteggio, possiamo concludere che il numero di possibili sequenze è n<sup>k</sup>.
'''Esempio''': L'insieme potenza di S, indicato con 2<sup>''S''</sup>, è l'insieme di tutti i sottoinsiemi di S. In insiemistica, 2<sup>''S''</sup> rappresenta l'insieme di tutte le funzioni da S a {0, 1}. Identificando una funzione in 2<sup>''S''</sup> con la corrispondente pre-immagine di uno, noi otteniamo una biunivocità tra 2<sup>''S''</sup> e i sottoinsiemi di S. In particolare, ogni funzione in 2<sup>S</sup> è la caratteristica funzione di un sottoinsieme di S.
Supponiamo che S sia finito con n = |S| elementi. Per ogni elemento di S, una caratteristica funzione in 2<sup>''S''</sup> è o zero o uno. Ci sono quindi 2<sup>''n''</sup> distinte funzioni caratteristiche da S a {0, 1}. Quindi il numero di sottoinsiemi distinti di S è dato da 2<sup>''n''</sup>.
'''Formule''' La formula del conteggio delle combinazioni ha alcuni casi speciali che vale la pena di memorizzare: ''nC0 = nCn = 1'' (C'è solo un modo per non raccogliere nessuna cosa e solo uno per raccogliere tutte le n cose.) ''nC1 = nC-1 = n'' (Ci sono n modi per raccogliere una cosa o per ometterne un'altra.) ''nCk = nCn-k'' (Ci sono lo stesso numero di modi per raccogliere k o n cose tanto quanto di ometterle.)
[[File:Powerset.png|senza_cornice|centro | '''Figura 10''']]
| |||