反対称的な２項関係の個数

質問

次の問題に対する解答と考え方を教えてください。

１からｎ上の自然数の集合S(n)={1,2,…,n}上の２項関係で、反対称的なものの個数はいくつか？

回答No.2

Tacosan

その対偶で考えてください. つまり
「x≠y ならば xRy でないか yRx でない」
です. すると, まず x≠y であるようなすべての x, y の組に対して
・xRy であって yRx でない
・yRx であって xRy でない
・xRy でも yRx でもない
の 3通りがあります. そしてこれはすべての組について独立なので全体で 3^(n(n-1)/2)通り.
一方 x=y のときには xRx でもそうでなくてもいいのでそれぞれについて 2通り, 全体で 2^n 通り.
これで全体の個数が分かります. 2^n 3^(n(n-1)/2)通りです.

回答No.1

Tacosan

「反対称関係」がどのような条件を満たすのかは分かりますか?

補足

xRy かつ yRx → x=y　ですよね？

これから個数をどう考えればいいのかがいまいちわかりません。