Matematické Fórum

Binární relace na množině C je podmnožina kart. součinu CxC, který má v našem případě 30 * 30 = 900  prvků .
Dále: n-prvková množina má 2^n podmnožin, tedy máme 2^900  relací.

↑ bojkot:
Relace R definovaná na množině C je symetrická, právěvě když pro libovolná a, b patřící co C platí  implikace    a R b  ==>  b R a .  Bez újmy na obecnosti můžeme pčedpokládat, že

C = {1, 2, ..., 30} .

Z pvků množiny CxC vybereme ty dvojice [x, y], kde x <= y  a sestavíme z nich množinu D.  Tvrdím, že relace R definovaná na množině C je symetrická právě tehdy, lze-li ji vyjádřit ve tvaru

R = A sjednoceno s B,    kde  A je částí D ,  B^(-1)  =  A \ I  ,

kde B^(-1) je inversní relace k relaci B  a  I je množina dvojic tvaru  [x,x] , kde x probíhá množinu C.  (Takové vyjádření lze pak zajistit jediným způsobem.) Symerická relace R je tedy jednoznačně určena již množinou A, neboť z uvdeného plyne

B = (A \ I)^(-1) .

Takže počet uvažovaných symetrických relací je roven počtu podmnožin množiny D, počet prvků množiny D je 465, jak jsi správně spočítal, takže počet našich sym. relací je skutečně 2^465.

I počet reflexivních relací sedí (každá z nich obsahuje množinu I, která má 30 prvků, a je tedy určena již podmnožinou v C \ I).

↑ bojkot: Odpověď jsem doplnil do svého předchozího příspěvku.

↑ bojkot: Další časové možnosti snad budu mít v pondělí. 
Pokud jde o transitivní relace definované na množině C, ty jsou charakterizované podmínkou  RoR je částí R, snad to půjde nějak využít.

EDIT. Přecejen jsem se ještě dostal aspoň k té AS. Využiji předchozích úvah a označení.
Každá AS  relace R dle našich podmínek je tvořena disjunktními podmnožinami A, B množiny D \ I  tak, že   R =  A U  B^(-1).
Nechť  a je počet prvků množiny A,  b poč. prvků množiny B.  Tedy

(1)          a + b  <= |D \ I| = 465 - 30 = 435 .

Nejprve zvolím a-prvkovou množinu A , mám na to  (435 nad a) možností, zbyde mi  435 - a  prvků pro volbu b-prvkové množiny B,
na což pak mám ((435 - a) nad b)  možností.

Počet možností, jak sestrojit AS relaci R =  A U  B^(-1) , kde |A| = a ,  |B| = b  , a, b jsou daná čísla  při podmínce (1),   je tedy

(2)               (435 nad a) * ((435 - a) nad b) ,

takže celkový počet AS relací získáme tak, že provedme dvojnásobnou sumu výrazu (2), kde bude sčítací index vnitřní sumy  b = 0 , ..., (435 - a) , 
sčítací index vnější sumy  a = 0 , ..., 435 .  Vnitřní sumace dá podle binomické věty

(3)               (435 nad a) * 2^(435 - a)  ,

to pak vnější sumace (opět podle binom. věty) sečte na  3^435.  Počet AS relací je tedy 3^435.
Mimochodem jsme dokázali, že 3^435 <  2^900.

Doufám jen, že je to správně.

↑ bojkot:
Pokud je v mém výpočtu AS relací je nějaká chyba, tak zatím se mi nedaří ji nalézt.


Antireflexivní relace jsou takové, které mají prázdný průnik s I, takže k jejich vytváření máme k disposici  n^2  - n   prvků (když z CxC odebereme I).  Proto počet AR relací je podle mne roven
2^(n^2  - n).

Každou reflexivní relaci dostaneme z nejaké antireflexivní tak, že k ní přidáme identitu I.  Reflexivních je proto stejný počet jako antireflexivních,  dohromady tedy
2*2^(n^2  - n) = 2^(n^2  - n + 1).

Tvůj druhý vzorec udává, domnívám se,  počet SLABĚ ANTISYMETRICKÝCH relací (pokud je správně můj výpočet AS relací).