X,Y,Z

[Omar931]

Sia X un insieme di cardinalità n appartenente ad N. Quante sono le coppie (Y,Z), dove Y e Z sono
sottoinsiemi di X, tali che Y intersecato Z = insieme vuoto?

[Palliit]

Ciao. Ci provo:

$2^n$.

[giannirecanati]

La sparo grossa. Secondo me il numero è \(\displaystyle 3^n \). Perchè per ogni elemento abbiamo 3 scelte, possiamo darlo Y oppure ad Z oppure a nessuno dei due.

[hamming_burst]

si parla di limitazioni superiori perchè $Y$ e $Z$ sono sottoinsiemi, consideriamo il caso di cardinalità e interseziona nulla massima, cioè quando$|Y|=|Z|=n/2 = \lfloor n/2 \rfloor$

$n$ pari: $n/2*n/2 = 1/4n^2$
$n$ dispari: $n/2*(n/2+1) = 1/4n^2 + n/2$

oppure tutti i possibili sottoinsiemi:
$n$ pari: $2^(n/2)*2^(n/2) = 2^n$
$n$ dispari: $2^(n/2)*2^(n/2+1) = 2^(n+1)$

[Palliit]

In effetti ho commesso un errore, sono partito dall'idea che i due sottoinsiemi Y e Z dovessero costituire una partizione di X, cosa non assegnata dal problema. Quindi la mia proposta di soluzione è infallibilmente sbagliata.

[giannirecanati]

Comunque se provate a farvi dei casi a mano piccoli non mi ritrovo con i risultati che dite, a me torna bene il \(\displaystyle 3^n \). E' facile vederlo anche con \(\displaystyle n=1,2 \).

[xunil1987]

Ci provo anche io!

Prendiamo un insieme $Y$ di cardinalità $k \leq n$. Ho $((n),(k))$ modi di sceglierlo e per ognuno di essi esistono $2^(n-k)$ insiemi $Z$ ad esso disgiunti, dunque per ogni $k$ esistono $((n),(k)) \cdot 2^(n-k)$ coppie $(Y,Z)$ di insiemi disgiunti. Sommando su $k$ ottengo $\sum_{k=0}^n ((n),(k)) \cdot 2^(n-k) = 3^n$ (per questa somma mi sono aiutato con WolframAlpha).

Ottimo intuito giannirecanati!

[giannirecanati]

Grazie ! Io l'avevo risolto con l'approccio combinatorico.
Comunque per la somma usiamo il binomio di Newton \(\displaystyle (a+b)^n=\sum_{k=0}^n \binom {n}{k}\cdot a^k\cdot b^{n-k} \), quindi \(\displaystyle \sum_{k=0}^n \binom {n}{k} \cdot 2^{n-k}\cdot 1^k=(2+1)^n=3^n \) .

[xunil1987]

Giusto, il binomio di Newton! Grazie!

[hamming_burst]

mmm che storia...non ci avevo pensato ai "modi di scegliere" del calcolo combinatorio. interessante