Numero di sottoinsiemi e cardinalità con calcolo combinatorio

Ho bisogno di voi per un problema di Calcolo Combinatorio sul numero di sottoinsiemi di una certa cardinalità e con almeno un elemento di un insieme. Non mi dilungo oltre e scrivo direttamente la traccia.

Si consideri il seguente insieme



Quanti sono i sottoinsiemi di di cardinalità quattro che contengono almeno un elemento tra 1, 2, 3, 4, 5?

Consideriamo il seguente insieme definito per caratteristica



Dobbiamo calcolare quanti sono i sottoinsiemi di di cardinalità quattro e tali che contengono almeno un elemento tra 1, 2, 3, 4, 5.

Il modo più furbo di risolvere il problema consiste nel:

(a) calcolare il numero totale di sottoinsiemi di di cardinalità quattro;

(b) calcolare il numero di sottoinsiemi di di cardinalità quattro che non contengono nessuno tra gli elementi 1, 2, 3, 4, 5.

(c) ricavare il numero di sottoinsiemi richiesto come differenza tra i risultati ottenuti nei punti (a) e (b).

Procediamo!


(a) Numero di sottoinsiemi di A di cardinalità quattro.

Gli elementi di sono i numeri naturali compresi tra 1 e 20 (estremi inclusi), dunque è formato da elementi distinti.

La cardinalità di un insieme finito è il numero di elementi che costituiscono l'insieme.

Di conseguenza calcolare il numero di sottoinsiemi di di cardinalità quattro equivale a calcolare il numero di sottoinsiemi di che hanno esattamente elementi e che possono essere estratti da un insieme che ne contiene .

Per capire come fare teniamo sotto mano lo schema risolutivo dei problemi di Calcolo Combinatorio e come prima cosa stabiliamo se l'ordine degli elementi è rilevante.

In un sottoinsieme l'ordine con cui si scrivono gli elementi non ha importanza, pertanto dobbiamo optare per le combinazioni. Semplici o con ripetizione?

Poiché un sottoinsieme non ammette ripetizioni di uno stesso elemento, il numero di sottoinsiemi di di cardinalità quattro è uguale al numero di combinazioni semplici di classe 4 di 20 elementi.

Usiamo allora la formula delle combinazioni semplici



e sostituiamo e .



Semplifichiamo il 16! a numeratore con quello del denominatore, calcoliamo il fattoriale di 4 e svolgiamo i calcoli che restano



Ci siamo! I sottoinsiemi di di cardinalità quattro sono 4845.


(b) Numero di sottoinsiemi di di cardinalità quattro che non contengono nessuno tra gli elementi 1, 2, 3, 4, 5

I sottoinsiemi di di cardinalità quattro che non contengono nessuno tra gli elementi 1,2,3,4,5 sono tanti quanti sono i sottoinsiemi di cardinalità quattro dell'insieme differenza



Questo insieme contiene elementi, e ragionando come nel caso (a) si ottiene che il numero di suoi sottoinsiemi di cardinalità è




(c) Numero di sottoinsiemi di di cardinalità quattro e con almeno un elemento tra 1, 2, 3, 4, 5

Come già scritto il numero di sottoinsiemi richiesto dalla traccia del problema è dato dalla differenza tra:

- il numero totale di sottoinsiemi di di cardinalità quattro, che sono 4845;

- il numero di sottoinsiemi di cardinalità quattro, che non contengono nessun elemento tra 1, 2, 3, 4 e 5, che sono 1365.



e il problema è risolto.

Altri riferimenti utili:

- permutazioni

- disposizioni

- combinazioni

- esercizi di riepilogo di calcolo combinatorio