|
10 - L'insieme delle parti di un n-insieme.
I coefficienti binomiali, oltre che nel calcolo dei coefficienti dei termini che si ottengono dalla potenza di un binomio, compaiono in numerose altre situazioni, anche le più inattese. Abbiamo già visto il modello delle biglie nelle scatole o quello dei percorsi per arrivare ai vari nodi di un reticolo.
Vediamo un altro esempio, completamente diverso: prendiamo un insieme A costituito da un numero finito n di elementi, si può costruire un insieme PA, costituito da tutti i sottoinsiemi di A, detto insieme delle parti di A. Ad esempio, da un insieme A = {a, b, c, d, e}, si possono ottenere tutti i seguenti sottoinsiemi:
| 1 | sottoinsieme vuoto | {} |
| 5 | sottoinsiemi con 1 elemento | {a},{b},{c},{d},{e} |
| 10 | sottoinsiemi con 2 elementi | {a,b},{a,c},{a,d},{a,e},{b,c},{b,d},{b,e},{c,d},{c,e},{d,e} |
| 10 | sottoinsiemi con 3 elementi | {c,d,e},{b,d,e},{b,c,e},{b,c,d},{a,d,e},{a,c,e},{a,c,d},{a,b,e},{a,b,d},{a,b,c} |
| 5 | sottoinsiemi con 4 elementi | {b,c,d,e},{a,c,d,e},{a,b,d,e},{a,b,c,e},{a,b,c,d} |
| 1 | sottoinsieme con 5 elementi | {a,b,c,d,e} |
La sequenza 1, 5, 10, 10, 5, 1 ci è ormai familiare: si tratta dei coefficienti binomiali della quinta riga del Triangolo di Pascal. Possiamo quindi affermare che il numero di sottoinsiemi di k elementi ciascuno, presi da un insieme di n elementi è dato dalle combinazioni di n elementi di classe k.
Quanti sono tutti i possibili sottoinsiemi? La combinatoria (l'arte del contare senza contare) ci dice che sono 2n, nel nostro caso 25 = 32.
|
