Úkoly z diskrétní matematiky, 3. série

Veškerá tvrzení precizně zdůvodněte.

(3.1) Nechť R je libovolná relace nad konečnou množinou X. Dokažte, že existují dvě různá čísla r, s ∈ ℕ taková, že R^{s} = R^{t}. 4 body

(3.2) Nechť X je n-prvková množina. Kolik existuje uspořádaných dvojic (A, B) takových, že:

(i) A ⊆ B ⊆ X 3 body (ii) A, B ⊆ X, A ≠ B 3 body