Matematické Fórum

Marty151 · 28. 10. 2014 12:42

Ahoj,
prosím o radu s tímto příkladem. Nevím vůbec kde začít.

Spočítejte kolik je trojic podmnožin A, B, C takových, že $A\subseteq B\subseteq C\subseteq \{1\ldots n\}$ .

Díky! :)

Brano · 28. 10. 2014 14:08

Nech $D=\{1,...,n\}$ .

Uvazuj $M=\mathcal P(D)\times\mathcal P(D)$ cize mnozinu lubovolnych dvojic $(P,Q)$ podmnozin mnoziny $D$ a mnozinu $N$ co bude mnozina lubovolnych trojic $(A,B,C)$ podmnozin mnoziny $D$ co splna $A\subseteq B\subseteq C$ .

Chceme dokazat, ze $|M|=|N|$ cize medzi nimi ideme najst bijekciu. Zoberme si zobrazenie $f:M\to N$ definovane takto $f(P,Q)=(P\cap Q,P,P\cup Q)$ (tie urcite splnaju pozadovane inkluzie). A zoberme si $g:N\to M$ definovane takto $g(A,B,C)=(B,A\cup[C\setminus B])$ . Nahliadni, ze $f(g(A,B,C))=(A,B,C)$ a ze $g(f(P,Q))=(P,Q)$ a teda $f$ je bijekcia a $g=f^{-1}$ .

Cize mame $|N|=|M|=2^n2^n$ .