Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /data/www/virtuals/matematika/html/wiki/includes/Sanitizer.php on line 1378
Počty relací na konečné množině – MatWiki

Počty relací na konečné množině

Z MatWiki

(Rozdíly mezi verzemi)
Přejít na: navigace, hledání
(Převedení části úloh z fóra na MatWiki)
(odstraněna neexistující kategorie)
 
Řádka 42: Řádka 42:
Prvky na úhlopříčce v relaci být nesmí, pro <math>n^2-n</math> ostatních prvků můžeme volit libovolně, proto <math>2^{n^2-n}</math> relací.
Prvky na úhlopříčce v relaci být nesmí, pro <math>n^2-n</math> ostatních prvků můžeme volit libovolně, proto <math>2^{n^2-n}</math> relací.
-
[[Kategorie:Vzorové úlohy]] [[Kategorie:Relace]]
+
[[Kategorie:Relace]]

Aktuální verze z 8. 3. 2014, 13:59

Zadání:Mějme konečnou množinu o n prvcích. Kolik na ní existuje

  1. symetrických
  2. antisymetrických
  3. reflexivních
  4. ireflexivních

relací?


Zdroj: Vlákno "relace" na forum.matweb.cz

Symetrické relace

Pojem relace je velmi základním pojmem v celé matematice a jeho pochopení je tedy velmi důležité. Nejdřív je dobré si uvědomit, co to relace je. Je to LIBOVOLNÁ podnožina kartézského součinu dvou (ne nutně různých) množin. To znamená, že relace nad množinou X je prostě nějaká podmnožina množiny uspořádaných dvojic (a, b), kde a i b patří do množiny X.

Relaci si mohu představit jako jakousi tabulku, kde prázné políčko znamená, že dva prvky nejsou v relaci a plné že naopak v relaci jou. Mějme třeba takovouto relaci na množině {1, 2, 3, 4, 5}. Řádky představují první prvek dvojice (a, b) a sloupce druhý.

   1  2  3  4  5
1 X
2    X      X
3    X  X
4 X         X
5        X     X

Ihned je třeba vidět, že tato relace je reflexivní.

Otázka kolik symetrických relací existuje nad n-prvkovou možinou se vlastně ptá na to, kolik existuje takových tabulek nxn symetrických podle hlavní diagonály. Více formálně:

Ptáme se, kolik existuje symetrických matic nxn nad tělesem LaTeX: \mathbb{Z}_{2} v závislosti na n.

Pro každý prvek na úhlopříčce nebo nad ní máme dvě možnosti, ostatní prvky matice jsou už dané. Prvků na úhlopříčce je n, prvků pod ní je LaTeX: (n-1)+(n-2)+\cdots+2+1=\frac{n(n-1)}2. Celkem máme LaTeX: 2^{n+\frac{n(n-1)}2}=2^{\frac{n(n+1)}2} možných symetrických relací.

Antisymetrické relace

Pro prvky nad úhlopříčkou můžeme volit ze dvou možností, prvky pod úhlopříčkou jimi jsou určeny. Prvky na úhlopříčce v relaci být nemohou. Možností je proto LaTeX: 2^{\frac{n(n-1)}2}

Reflexivní relace

Prvky na úhlopříčce v relaci být musí, pro LaTeX: n^2-n ostatních prvků můžeme volit libovolně, proto LaTeX: 2^{n^2-n} reflexivních relací.

Ireflexivní relace

Prvky na úhlopříčce v relaci být nesmí, pro LaTeX: n^2-n ostatních prvků můžeme volit libovolně, proto LaTeX: 2^{n^2-n} relací.