Matematické Fórum

Kein · 18. 11. 2009 23:23

Zdravím...

Měl bych dotaz ohledně uspořádaných dvojic...

Mám příklad: Kolik je uspořádaných dvojic $(A,B)$ , kde $A \subseteq B \subseteq \{1,2,...n}$ . Podrobně zdůvodněte.

Podle toho, co jsem se dočetl, vzniká uspořádaná dvojice při kartézském násobení množin, tedy $A \times B =\{(a,b);a \in A, b \in B }$ .

Došel jsem k závěru, že počet uspořádaných dvojic je $({a_n \cdot b_n})$

Ovšem nejsem si svým tvrzením jistý...

Olin · 19. 11. 2009 14:09 — Editoval Olin (19. 11. 2009 15:43)

A co je $({a_n \cdot b_n})$ ? Co jsou $a_n$ a $b_n$ ?

Při kartézském násobení nevznikají uspořádané dvojice, ale množiny uspořádaných dvojic - jak píšeš, $A \times B =\{(a,b);a \in A, b \in B \}$ . My ale nechceme uspořádané dvojice prvků A a B (které jsou prvky $A \times B$ ), ale přímo dvojice (A, B) (ty jsou prvky $\mathcal{P}(\{1,\dots,n\}) \times \mathcal{P}(\{1,\dots,n\})$ , kde $\mathcal{P}$ značí potenční množinu).

Uvedu příklad toho, co hledáme, pro n = 3. Všechny uspořádané dvojice vyhovující zadání jsou:
$(\emptyset,\,\emptyset);\, (\emptyset,\,\{1\});\, (\emptyset,\,\{2\});\, (\emptyset,\,\{3\});\, (\{1\},\,\{1\});\, (\{2\},\,\{2\});\, (\{3\},\,\{3\});\nl (\emptyset,\,\{1,2\});\, (\emptyset,\,\{1,3\});\, (\emptyset,\,\{2,3\});\, (\{1\},\,\{1,2\});\, (\{2\},\,\{1,2\});\, (\{1\},\,\{1,3\});\, (\{3\},\,\{1,3\});\, (\{2\},\,\{2,3\});\, (\{3\},\,\{2,3\});\nl (\{1, 2\},\,\{1,2\});\, (\{1, 3\},\,\{1,3\});\, (\{2, 3\},\,\{2,3\});\nl (\emptyset,\,\{1,2,3\});\, (\{1\},\,\{1,2,3\});\, (\{2\},\,\{1,2,3\});\, (\{3\},\,\{1,2,3\});\, (\{1, 2\},\,\{1,2,3\});\, (\{1, 3\},\,\{1,2,3\});\, (\{2, 3\},\,\{1,2,3\});\, (\{1,2,3\},\,\{1,2,3\})$ .

Rumburak · 19. 11. 2009 15:29

↑ Kein:
1. Zvolme pevně množinu $B \subseteq \{1,2,...n}$ , počet jejích prvků označme $m$ . Její podmnožinu $A$ pak můžeme volit
$2^m$ způsoby, tedy k výše zvolené m-prvkové množině $B$ existuje $2^m$ usp. dvojic $[A, B]$ splňujících požadovanou podmínku.

2. Je-li dáno přiroz. číslo $m \le n$ (za přirozené číslo zde považujeme též nulu, která odpovídá počtu prvku prázdné množiny),
pak m-prvkovou množinu $B \subseteq \{1,2,...n}$ lze zvolit $${n \atop m}$$ způsoby, takže máme celkem $${n \atop m}$\cdot 2^m$ usp. dvojic $[A, B]$ ,
v nichž množina $B$ je přesně m-prvková.

3. Počet prvků množiny $B$ může být libovolný od 0 do n, čemuž odpovídá konečný výsledek $\sum_{m=0}^{n}${n \atop m}$\cdot 2^m = 3^n$
- viz binomický rozvoj $(2 + 1)^n$ .

Olin · 19. 11. 2009 15:41

↑ Rumburak:
Nechtěl jsem hned psát celé řešení, protože problém byl zjevně jen v nepochopení zadání, ale nevadí :-) Dá se na to nahlédnout ještě jinak - každý prvek buď není ani v jedné množině, nebo je jen v B, nebo je v A i B. Celkem 3 možnosti pro každý prvek, tedy $3^n$ dvojic.

Rumburak · 19. 11. 2009 15:52

↑ Olin:
Tak to je pěkné řešení !

Matematické Fórum

#1 18. 11. 2009 23:23

Množiny - uspořádané dvojice

#2 19. 11. 2009 14:09 — Editoval Olin (19. 11. 2009 15:43)

Re: Množiny - uspořádané dvojice

#3 19. 11. 2009 15:29

Re: Množiny - uspořádané dvojice

#4 19. 11. 2009 15:41

Re: Množiny - uspořádané dvojice

#5 19. 11. 2009 15:52

Re: Množiny - uspořádané dvojice

Zápatí