Indice di tutti gli articoli di Umberto presenti in archivio-Matematica

Adesso che conosciamo la formula del binomio di Newton, possiamo affrontare delle simpatiche applicazioni, che volevo proporre sotto forma di quesiti, comprensivi di soluzione. Chi vuole  può provare da solo.

Dato un  insieme di n elementi, quanti sono i suoi sottoinsiemi? Risolvere questo problema usando la formula del binomio di Newton.

Soluzione.

Stiamo cercando quanti sono gli elementi dell'insieme delle parti. Avevamo risolto il problema altro modo qui , usando il sistema binario.

Per risolvere il quesito, ci appoggiamo  dapprima al calcolo combinatorio, di cui abbiamo visto qualcosa qui.

Supponiamo che l'insieme X abbia n elementi ; l'insieme P(x) sarà formato da sottoinsiemi con 0 , 1,2,...n elementi. cerchiamo perciò , per ogni k=0,1,..n delle k-uple che consideriamo uguali anche se non hanno lo stesso ordine. Ad esempio (a,b) rappresenta lo stesso sottoinsieme di (b,a). Quanti sono le coppie che possiamo estrarre da X? Il primo elemento lo possiamo scegliere in n modi, il secondo in n-1 modi. Quindi n(n-1). In tal modo ottengo però le coppie ordinate, ma nei sottoinsiemi non conta l'ordine con cui consideriamo gli elementi. Quindi dobbiamo dividere per le permutazioni di 2, cioè 2!. Otteniamo allora n(n-1)/2! e per k=3? n(n-1)(n-2)/3! In generale, il termine in funzione di k viene:

che si può anche scrivere in altro modo:

.

Infatti:

Questo termine lo abbiamo già visto , e rappresenta il coefficiente binomiale.

Quindi, per ottenere il numero di tutti i sottoinsiemi di X, dobbiamo sommare questi termini da 0 a n:

che possiamo  anche riscrivere:

 che rappresenta proprio lo sviluppo di un binomio in cui a=b=1. Per concludere:

se indichiamo con  C(P(x)) il numero di sottoinsiemi di X, avremo allora:

.