Matematické Fórum

eminich · 23. 03. 2012 08:36

Zdravim,
neviem si rady s tymto: kolkymi sposobmi mozeme z n-prvkovej mnoziny vybrat 3 podmnoziny tak ze platia tieto podmienky zaroven

$A\cap B\cap C=\emptyset$
$A\cap B\neq\emptyset$
$A\cap C\neq\emptyset$

Dakujem

Rumburak

↑ eminich:

Ahoj.

Takže je dána $n$ -prvková množinu $M$ , z jejíchž prvků máme sestavit množiny $A, B, C$ stanovených vlastností

(0) $A\cap B\cap C=\emptyset$ ,

$A\cap B\neq\emptyset$ , $A\cap C\neq\emptyset$

a ptáme se, kolika způsoby to lze provést.

Předpokládejme, že takové množiny $A, B, C$ existují . Existují tedy též prvky $b \in A\cap B\neq\emptyset$ , $c \in A\cap C\neq\emptyset$ , při čemž
z podmínky (0) plyne $b \ne c$ (při $b = c$ by podmínka (0) byla porušena). Tím jsme odvodili, že aby množiny $A, B, C$ požadovaných
vlastností existovaly, nutně musí být $n \ge 2$ .

Případ $n = 2$ , tj. $M = \{b, c\}, b \ne c$ , má zřejmě 2 řešení, a sice

$A = M, B = \{b\}, C = \{c\}$ , resp. $A = M, B = \{c\}, C = \{b\}$

(tato řešení se však liší pouze formálně - označením množin - nikoliv věcně. Nicméně bude možná výhodnější přijmout alespoň pro začátek
tento formální pohled).

Počet možností, jak požadovaným způsobem sestavit množiny A, B, C pro $n = 2, 3, 4 , ...$ označme $y_n$ . Mezi nimi je $x_n$ takových,
kdy množiny $A, B, C$ navíc splňují podmínku

(1) $A\cup B\cup C= M$ .

Pro $n = 2$ tedy již máme $y_n = x_n = 2$ .

Zkus nejprve nejprve určit jednodušší posloupnost $(x_n ; n = 2, 3, ... )$ tak, že pro její členy najdeš rekurentní vztah.

Matematické Fórum

#1 23. 03. 2012 08:36

kombinatorika

#2 24. 03. 2012 13:40 — Editoval Rumburak (24. 03. 2012 14:04)

Re: kombinatorika

Zápatí