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\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze