Matematické Fórum

Kein · 28. 12. 2009 20:15

Zdravím
Potřeboval bych si ujasnit nějaké věci.

Měl bych zadání:
Kolik je uspořádaných dvojic $(A,B)$ , kde $A,B \subseteq \{1,2,...n \}$ a $\left |A \cap B \right |=1?$

Teda jedná-li se o potenční množinu, potom $\mathcal{P}(A \{1,2,...n \}) \times \mathcal{P}(B \{1,2,...n \}=3^{n})$ - nebo se zde pletu?

Potom když $\left |A \cap B \right |=1$ , pak budu mít $n-1$ průniků a výsledek mi vyjde $3^{(n-1)}$ .

Je tento postup správný a nebo někde dělám chybu?

Wotton · 29. 12. 2009 09:41

Mám dojem, že to není úplně to co máš dělat.
$\mathcal{P}(A \{1,2,...n \}) \times \mathcal{P}(B \{1,2,...n \})=3^{n}$ Tento zápis nechápu co má znamenat. Hlavně co myslíš výrazem $A \{1,2,...n \}$ .

Měl bys hledat A, B takový, že $A\in\mathcal{P}(\{1,2,\dots,n\})$ a $B\in\mathcal{P}(\{1,2,\dots,n\})$

Kein · 30. 12. 2009 19:39

Chtěl jsem napsat tohle, nějak jsem zapoměl na to "=" $\mathcal{P}(A= \{1,2,...n \}) \times \mathcal{P}(B= \{1,2,...n \})=3^{n}$

Nebo by se to dalo napsat $\mathcal{P}(A) \times \mathcal{P}(B)$

A pokud vím, že $\mathcal{P}(A) = 2^n$ , potom pro $A=\{1,2,3\}$ a $B=\{1,2,3\}$ , teda $A \{1,2,3 \} \times B \{ 1,2,3 \}=27$ , tedy $3^n$ dvojic.

A jestli tam pak mám $\left |A \cap B \right |=1$ , potom mám tři možnosti kde může ta 1 být...buď v A, nebo v B, a nebo v A i v B...

check_drummer · 31. 12. 2009 12:10

↑ Kein:

Nepochopil jsem přesně tvou poslední úvahu o n-1 průnicích. Můj postup je následující:

Množinu A zvolme libovolně, aby měla aspoň jeden prvek, těchto možností je: $\sum_{k=1}^{n}{{n}\choose{k}}$ . Ke každé takové množině A vyberu všechny množiny B, které mají s A prázdný průnik. To jsou všechny podmnožiny (n-k) prvkové množiny, tedy jich je $2^{n-k}$ . Aby množiny A a B měly právě jednoprvkový průnik, obohatíme každou množinu B o jeden prvek z množiny A - těchto možností je k a tedy možných množin B je $k2^{n-k}$ a tedy možných dvojic A, B je $\sum_{k=1}^{n}{{n}\choose{k}}k2^{n-k}$ . Nyní použijeme kombinatorické identity: ${{n}\choose{k}}k = n{{n-1}\choose{k-1}}$ , pak $\sum_{k=1}^{n}{{n}\choose{k}}k2^{n-k} = n\sum_{k=1}^{n}{{n-1}\choose{k-1}}2^{n-k} = n\sum_{k=0}^{n-1}{{n-1}\choose{k}}2^{n-k-1} = n\sum_{k=0}^{n-1}{{n-1}\choose{k}}2^{k} = n3^{n-1}$ . Poslední rovnost je použití binomické věty.

Tedy požadovaných dvojic je $n3^{n-1}$ .

check_drummer · 31. 12. 2009 12:13

↑ Kein:

Všech možných dvojic (pokud neuvažujeme podmínku jednoprvkového průniku) je $4^n$ .

Olin · 31. 12. 2009 12:58 — Editoval Olin (31. 12. 2009 12:59)

Podle mě nejrychlejší postup:
Zvolím společný prvek (n způsobů), zbývajících n - 1 prvků buď dám do A, nebo do B, nebo ani do jedné (3 možnosti, tj. $3^{n-1}$ způsobů). Celkem $n 3^{n-1}$ způsobů.

Matematické Fórum

#1 28. 12. 2009 20:15

Uspořádané dvojice

#2 29. 12. 2009 09:41

Re: Uspořádané dvojice

#3 30. 12. 2009 19:39

Re: Uspořádané dvojice

#4 31. 12. 2009 12:10

Re: Uspořádané dvojice

#5 31. 12. 2009 12:13

Re: Uspořádané dvojice

#6 31. 12. 2009 12:58 — Editoval Olin (31. 12. 2009 12:59)

Re: Uspořádané dvojice

Zápatí