Zlicznie relacji antysymetrycznych

[murek1993]

Czy może ktoś wie jak zliczyć relacje antysymetryczne? Np symetrycznych będzię \(\displaystyle{ 2^{(n-1)n/2}}\) a zwrotnych \(\displaystyle{ 2^{(n-1)n}}\)

[Medea 2]

Relacja antysymetryczna to taka, że \(\displaystyle{ a R b}\) i \(\displaystyle{ b R a}\) pociągają \(\displaystyle{ a = b}\)? Jeśli tak, to zastanów się, ile masz wyborów na to, czy \(\displaystyle{ a R a}\) dla wybranego \(\displaystyle{ a}\), a ile na to, czy \(\displaystyle{ a R b}\) dla \(\displaystyle{ a < b}\) (porządek bierze się stąd, że elementy zbioru można ponumerować).

[murek1993]

2N?

[Medea 2]

Zastanów się jeszcze raz. Zbiór ma \(\displaystyle{ n}\) elementów, więc to, czy \(\displaystyle{ a R a}\) zachodzi / nie zachodzi, można ustalić na jeden z \(\displaystyle{ 2^n}\) sposobów. A co z pozostałymi?

[murek1993]

Jeśli by to obliczać na przykładzie macierzy to od calosci czyli \(\displaystyle{ n^{2}-n}\) czyli odejmujemy przekątną bo nalezy do relacji oraz reszta elementow ktore naleza do relacji dzielone na dwa. Na przykładzie takiej macierzy o nagłówku poziomym b \(\displaystyle{ \left|3,4,6,8 \right|}\) i takim samym poziomym a nagłowku a to do relacji naleza pary na przekątnej \(\displaystyle{ 3,3}\) \(\displaystyle{ 4,4}\) \(\displaystyle{ 6,6}\) \(\displaystyle{ 8,8}\)
a takze do relacji naleza pary \(\displaystyle{ 3,6}\) \(\displaystyle{ 4,8}\) tylko jesli jest n elementow to nie da sie zliczyc notacja z n .

[Medea 2]

Da się zliczyć. Nie mam pojęcia, o jakich nagłówkach poziomych mówisz, ale... jeżeli ustalisz przekątną, to które z poniższych przypadków mogą zajść dla \(\displaystyle{ a \neq b}\)?

• \(\displaystyle{ a R b}\), \(\displaystyle{ b R a}\)
• \(\displaystyle{ \neg (a R b)}\), \(\displaystyle{ b R a}\)
• \(\displaystyle{ a R b}\), \(\displaystyle{ \neg(b R a)}\)
• \(\displaystyle{ \neg(a R b)}\), \(\displaystyle{ \neg(b R a)}\)

[murek1993]

Przypadek 2,3,4