Calcolo Combinatorio

CALCOLO COMBINATORIO

In molti casi il numero dei punti campione nello spazio dei campioni non è molto grande e non vi è allora alcuna difficoltà nel contare i punti campione che servono per la determinazione delle probabilità. Tuttavia alcune volte può essere difficile, o almeno noioso, determinare per elencazione diretta gli elementi in uno spazio dei campioni finito. E’ preferibile avere dei metodi per contare il numero di tali elementi senza elencarli. Il calcolo combinatorio fornisce dei metodi per calcolare il numero di elementi di un insieme.

1. Principio fondamentale del contare Per illustrare il problema si consideri il seguente esempio. Esempio Se un uomo ha 2 camicie e 4 cravatte, quanti modi ha per scegliere una camicia e poi una cravatta? Per trattare problemi di questo tipo è utile disegnare un diagramma ad albero. Se indichiamo le camicie con C1 e C2 e le cravatte con T1, T2, T3 e T4 allora i vari modi di scegliere una camicia e poi una cravatta sono indicati dal diagramma ad albero della fig.1.

Fig. 1

Seguendo un dato cammino da sinistra verso destra lungo i rami dell’albero, si ottiene una particolare scelta, cioè un elemento dello spazio dei campioni, e si può vedere che le possibilità di scelta sono 8. Questo risultato può essere ottenuto osservando che ci sono 2 rami C, che ciascun ramo C si divide in 4 rami T; ci sono quindi 2 · 4 = 8 combinazioni possibili (cammini). Vale il seguente risultato generale. Se gli insiemi A1, A2,…, Ak contengono rispettivamente n1, n2, …, nk oggetti, il numero di modi diversi di scegliere prima un oggetto di A1, poi un oggetto di A2,…, infine un oggetto di Ak è N = n1 · n2 · … · nk

1

(1)

2. Disposizioni 2.1 Disposizioni con ripetizione Se in particolare n1 = n2 = …= nk = n, si ha N = nk, che rappresenta il numero delle disposizioni con ripetizione di n oggetti a gruppi di k, ossia dei gruppi che si possono formare scegliendo k oggetti, anche ripetibili, fra n oggetti disponibili, che si indica con

D

(r) = nk n, k

(2)

Esempio Nella schedina del totocalcio tutti i possibili pronostici sono dati dalle disposizioni con ripetizione dei tre elementi 1 2 X a gruppi di 13 (i tre simboli si possono ripetere); il loro numero è (r) D 3,13 = 313 = 1594323 2.2 Disposizioni semplici Definizione. Dati n oggetti distinti, si chiamano disposizioni semplici (senza ripetizione) i gruppi che si possono formare scegliendo k (k ≤ n) degli n oggetti; i gruppi devono differire o per qualche oggetto o per l’ordine in cui sono disposti. Per trovare una formula per il numero delle disposizioni di k oggetti scelti da un insieme di n oggetti distinti, si osservi che la prima scelta è fatta dall’intero insieme di n oggetti, la seconda è fatta fra gli n – (k – 1) = n – k + 1 oggetti rimanenti dopo le prime k – 1 scelte. Pertanto, per la (1), il numero delle disposizioni è

D

n, k

= n(n − 1)(n − 2)...(n − k + 1)

Si può usare la notazione del fattoriale n! = 1·2·3·…·n. Moltiplicando e dividendo per (n – k)! si ottiene D

n, k

=

n(n − 1)...(n − k + 1)(n − k)! n! = (n − k)! (n − k)!

Pertanto, il numero delle disposizioni semplici (senza ripetizione) di k oggetti scelti da un insieme di n oggetti distinti è dato da n! D = n(n − 1)(n − 2)...(n − k + 1) = (3) n, k (n − k)! Esempio Quante parole di 3 lettere diverse si possono formare con l’alfabeto di 21 lettere? Sono le disposizioni semplici di 21 oggetti diversi a gruppi di 3 D 21,3 =

21! 21! = = 21 ⋅ 20 ⋅ 19 = 7980 (21 − 3)! 18!

2

3. Permutazioni 3.1 Permutazioni di n oggetti distinti Definizione. Le permutazioni di n oggetti distinti sono tutti i gruppi formati ciascuno da tutti gli n oggetti dati e che differiscono solo per l’ordine degli oggetti. Ponendo k = n nella formula delle disposizioni semplici si ottiene il seguente risultato. Il numero delle permutazioni di n oggetti distinti è dato da P = n! n

(4)

Esempio Si fanno sedere 5 uomini e 4 donne in fila: in quanti modi le donne possono occupare i posti pari? Gli uomini possono essere sistemati in 5! modi diversi, le donne in 4! modi diversi. Ciascuna sistemazione degli uomini può essere associata ad ogni sistemazione delle donne, quindi il numero complessivo di sistemazioni è N = 5! · 4! = 2880 3.2 Permutazioni di n oggetti non tutti distinti Supponiamo che un insieme sia formato da n oggetti non tutti distinti, dei quali cioè n1 sono di un tipo (indistinguibili), n2 di un secondo tipo,…, nk del k-esimo tipo, con n1 + n2 + … + nk = n. Il numero delle permutazioni di n oggetti non tutti distinti è dato da n! P = (5) n, n 1 , n 2 ,..., n k n 1!n 2 !... n k ! Esempio 5 palline rosse, 2 bianche e 3 azzurre devono essere sistemate in fila; se tutte le palline dello stesso colore sono indistinguibili, quante sistemazioni sono possibili? Il numero delle possibili sistemazioni è N=

10! = 2520 5! ⋅ 2! ⋅ 3!

Osservazione. Gli anagrammi, cioè le parole che si ottengono da una parola qualunque cambiando solo il posto delle sue lettere, sono permutazioni. Esempio 1 Contare gli anagrammi della parola ROMA. La parola è formata da 4 lettere tutte diverse; gli anagrammi sono in numero di N = 4! = 24 Esempio 2 Contare gli anagrammi della parola MATEMATICA. La parola contiene 10 lettere di cui 2M, 3A, 2T; gli anagrammi sono in numero di 10! N= = 151200 2! ⋅ 3! ⋅ 2!

3

4. Combinazioni In una disposizione semplice siamo interessati all’ordine degli oggetti, quindi ad esempio il gruppo “abc” è un gruppo diverso da “bac”; se invece l’ordine di scelta non interessa, cioè “abc” e “bca” sono lo stesso gruppo, si ottengono le combinazioni. Definizione. Le combinazioni sono tutti i gruppi di k oggetti, che si possono formare da un insieme di n oggetti distinti, in modo che i gruppi differiscano per almeno un oggetto. Il numero delle combinazioni di n oggetti a gruppi di k è dato da

D n, k n n!   = C = = n, k k! k!(n − k)! k

(6)

I numeri n n! n(n − 1)...(n − k + 1)   = = k!  k  k!(n − k)! sono chiamati coefficienti binomiali, perchè compaiono nello sviluppo della potenza del binomio di Newton (a + b)n. Esempio 1 In quanti modi si possono scegliere 3 carte da 8 diverse? Il numero delle scelte è dato dalla combinazioni di 8 carte a gruppi di 3  8 8! 8! C8,3 =   = = = 56  3  3! ⋅ (8 − 3)! 3!⋅5! Esempio 2 Quante squadre di calcio si possono formare con 30 giocatori? Il numero è dato dalle combinazioni di 11 giocatori scelti nell’insieme di 30  30  30! C 30,11 =   = = 54627300 11  11! ⋅ 19! Esempio 3 In quanti modi 10 oggetti diversi possono essere suddivisi in due gruppi contenenti rispettivamente 4 e 6 oggetti? Il problema è equivalente a quello di cercare il numero delle scelte di 4 oggetti a partire da 10 (o di 6 a partire da 10), non avendo alcuna importanza l’ordine di scelta; si calcolano perciò le combinazioni 10  10! C10,4 =   = = 210  4  4! ⋅ 6!

4