Počet relací
Úloha číslo: 3352
Určete počet relací na čtyřech (\(n\)) prvcích:
– všech,
– reflexivních,
– symetrických,
– antisymetrických.
Řešení
Relaci si znázorníme pomocí matice sousednosti \(n\times n\) obsahující jedničky a nuly. Tato matice má \(n^2\) prvků.
Počítáme-li včechny relace, můžeme těchto \(n^2\) prvků zvolit libovolně.
U reflexivních relací jsou předepsané jedničky na diagonále, zbylých \(n^2-n\) prvků lze zvolit libovolně.
U symetrických relací jsou prvky souměrné podle diagonály stejné, postačí zvolit prvky na diagonále a nad ní, a potom prvky pod diagonálou doplnit symetricky.
U antisymetrických je třeba odlišit prvky na diagonále od dvojic čísel umístěných symetricky podle diagonály. Prvky na diagonále mohou nabýbat dvou hodnot, zatímco u dvojic jsou tři možnosti: oba prvky 0, pod diagonálou 0 a nad 1 a opačně (oba prvky ve dvojici nemohou být 1 zároveň).
Odpověď
Počet všech relací je \(2^{n^2}\), což pro \(n=4\) dává \(2^{16}=65536\).
Reflexivních relací je \(2^{n^2-n}\), pro \(n=4\) dává \(2^{12}=4096\).
Symetrických relací je \(2^{\frac{n^2+n}2}\), což pro \(n=4\) dává \(2^{10}=1024\).
Antisymetrických relací je \(2^n\cdot 3^{\frac{n^2-n}2}\), což pro \(n=4\) dává \(2^4{\cdot} 3^6=16{\cdot} 729=11664\).