Numero di sottoinsiemi e cardinalità con calcolo combinatorio

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Numero di sottoinsiemi e cardinalità con calcolo combinatorio #65432

avt
bee89
Punto
Ciao a tutti, vi scrivo per un esercizio sul numero di sottoinsiemi e sulla cardinalità. Prima di scrivere questo post ho verificato che non fossero presenti altri esercizi e ho trovato una sola discussione inoltrata da "martygigugin" e credo che l'impostazione per risolvere il mio problema sia la stessa, qualcuno potrebbe aiutarmi?

Allora: sia dato l'insieme

A =\{a_1, \ a_2, \ a_3, \ a_4, \ a_5, \ a_6, \ a_7, \ a_8\}

ed il suo sottoinsieme

B =\{a_1, \ a_2, \ a_3, \ a_4, \ a_5\}

Quanti sono i possibili sottoinsiemi C di A tali che la cardinalità di B intersecato C sia =2 ?


La risposta che fornisce il testo è 80, ma non riesco a pervenire al risultato. grazie in anticipo per il vostro eventuale aiuto...emt


PS: per tentare di risolvere l 'esercizio ho provato a ricavare l'insieme C dall'unione di A e B, dopo di che ho tolto da B gli elementi di C e il risultato lo calcolato come il rapporto degli elementi di C sotto forma fattoriale! diviso gli elementi suggeriti dal testo, ovvero 2 ! ma niente... emt
 
 

Numero di sottoinsiemi e cardinalità con calcolo combinatorio #65445

avt
Galois
Amministratore
Ciao bee89 e benvenuto/a in YouMath! emt

Un'analisi preliminare sull'insieme C ci permetterà di concludere quasi immediatamente l'esercizio.

Innanzitutto C deve essere un sottoinsieme dell'insieme A e la sua cardinalità deve essere tale che:

\mbox{card}(B \cap C)=2

Per definizione di intersezione tra insiemi, la cardinalità dell'intersezione tra B e C è uguale a 2 se

C contiene esattamente 2 elementi che sono già contenuti in B.

ovvero esattamente 2 elementi di C devono essere scelti tra

\{a_1, \ a_2, \ a_3, \ a_4, \ a_5\}

In quanti modi li possiamo scegliere? In

\dbinom{5}{2} = \frac{5!}{2!(5-3)!}=10 \ \mbox{modi}

Abbiamo cioè fatto ricorso alle combinazioni semplici di k=2 elementi scelti tra n=5.

Abbiamo quindi già ottenuto 10 possibili modi in cui può essere formato il sottoinsieme C.
Infatti se C contiene solo due elementi ed essi sono stati scelti dagli elementi di B allora sarà tale che:

\mbox{card}(B \cap C)=2

Questo però non conclude il nostro esercizio! Nulla vieta infatti che C possa contenere più di due elementi.

Attenzione ora! Abbiamo già detto, ma lo ripeto, che C deve contenere 2 e soltanto 2 elementi scelti dall'insieme B

I restanti elementi di C possono essere scelti dall'insieme A a patto però che essi non appartengano a B, ovvero li possiamo scegliere dall'insieme differenza:

A-B=\{a_6, \ a_7, \ a_8\}

Morale: l'insieme C potrà essere formato da 2, 3, 4, o al massimo 5 elementi:

2 di essi saranno tali da appartenere anche a B, gli altri tali da appartenere ad A-B

Quindi, dopo questo ragionamento possiamo concludere che:

- I sottoinsiemi C di due elementi saranno 10 (prima trovati)

- Quelli di 3 elementi saranno della forma:

\{\alpha, \beta, \spadesuit \}

dove \{\alpha, \ \beta\}

possono essere scelti in 10 modi (esattamente come prima! Sono i due che devono appartenere a B) e il restante \spadesuit deve essere uno tra a_6, \ a_7, \ a_8

Quindi, in tutto, avremo 3 sottoinsiemi formati da 3 elementi e tali da soddisfare l'ipotesi iniziale.

- Quelli di 4 elementi saranno della forma:

\{\alpha, \beta, \spadesuit\, \ \bigstar \}

con

\alpha, \beta \in B

che potrò scegliere in 10 modi

e \{\spadesuit\, \ \bigstar \} \in A-B (di cardinalità 3) che potrò scegliere in

\dbinom{3}{2}=3 \ \mbox{modi}

Ovvero un totale di 3 \cdot 10 = 30 sottoinsiemi di 4 elementi

Infine:

- quelli di 5 elementi saranno quelli della forma:

\{\alpha, \ \beta, \ a_6, \ a_7, \ a_8\}

con \alpha e \beta che, come sempre, potranno variare in 10 modi.. Quindi in tutto avrò 10 sottoinsiemi di 5 elementi.

Sommando i vari risultati avrò un totale di 80 sottoinsiemi da poter formare e tali da soddisfare la richiesta emt

-------------------------------------

Questo tutto il ragionamento, fatto nel dettaglio con la speranza di farti capire.

In sede d'esame sarebbe bastato scrivere:

I sottoinsiemi C di A che soddisfano la nostra richiesta sono tutti e soli quelli del tipo:

\{\beta_1, \beta_2\}

\{\beta_1, \beta_2, \ \beta_3\}

\{\beta_1, \beta_2, \ \beta_3, \ \beta_4\}

\{\beta_1, \beta_2, \ \beta_3, \ \beta_4, \ \beta_5\}

con:

\beta_1, \beta_2 \in B

\beta_i \in A-B=\{a_6, \ a_7, \ a_8\}, \ \forall i \in \{3,4,5\}

Ora, osservando che tutti i possibili sottoinsiemi hanno \beta_1, \ \beta_2 come loro elementi e questi possono essere scelti in:

\dbinom{5}{2}=10 \ modi

abbiamo che:

I sottoinsiemi del tipo

\{\beta_1, \beta_2\}

sono esattamente 10

\{\beta_1, \beta_2, \ \beta_3\}

sono 10 \cdot 3 = 30

in quanto \beta_3 può essere uno tra a_6, \ a_7, \ a_8

\{\beta_1, \beta_2, \ \beta_3, \ \beta_4\}

sono 10 \cdot 3 = 30

poiché \beta_3, \ \beta_4 possono essere scelti in

\dbinom{3}{2}=3 \ \mbox{modi}

poiché appartengono ad un sottoinsieme di 3 elementi

\{\beta_1, \beta_2, \ \beta_3, \ \beta_4, \ \beta_5\}

sono 10 \cdot 1 = 10

in quanto, per forza di cose, \beta_1, \ \beta_2, \ \beta_3 devono coincidere con a_6, \ a_7, \ a_8 e l'ordine di scelta non conta.

---------------------

Chiudo invitandoti a dare un'occhiata ai link che trovi e a fare un'attenta lettura: come si risolvono i problemi di calcolo combinatorio
Ringraziano: Omega, Pi Greco, CarFaby

Re: Numero di sottoinsiemi e cardinalità con calcolo combinatorio #65497

avt
bee89
Punto
grazie mille sei stato ESAUSTIVISSIMISSIMO emt

...non so se posso chiederlo, ma tentar non nuoce..

[Mod-Galois] Esercizio rimosso. Vedi messaggio successivo [/Mod]
Ringraziano: Galois

Re: Numero di sottoinsiemi e cardinalità con calcolo combinatorio #65505

avt
Galois
Amministratore
Prego emt

Puoi chiedere eccome, ma non qui! Come da regolamento, ogni topic deve trattare un solo argomento con annesso tentativo emt
Ringraziano: bee89
  • Pagina:
  • 1
Os