プロが教える店舗&オフィスのセキュリティ対策術

以下の問題の解答がわかりません。解答とできれば考え方を教えてください。
S={1,2,...,n}において、S上の2項関係で反射的かつ対称的なものは全部で何個存在するか。

A 回答 (2件)

ご存知かもしれませんが、集合論ではS上の2項関係とは、S×S(直積)の部分集合であることに注意しましょう。

Rが二項関係の時、aRb は(a,b)がRの元になっているということです。

そうすると、反射的とは、対角成分をもつということ。
対称的は、n×nのマスの対角線についてRが線対称になってるということです。

例えば、1だけ関係を持たせたいとしたら、R={(1,1)}とすれば、反射的かつ対称的です。
1と2にだけ関係を持たせたいとしたら、R={(1,1) (2,2) (1,2) (2,1)}とすれば良いです。

Sから、何か(自身を含む)と関係をもたせるものとして、k個選んできます。(nCk通り)

k=1のときは、反射的、かつ対称的な関係は、最初に挙げた例のようにするしかありません。

kが2以上の時
選んだもの全体を、便宜的にXとします。
反射的にするために、Xの各元xについて対角成分(x,x)をとります。これでXのどの元も自身と関係を持ったことになります。

次に異なる元との関係について。つまり対角成分以外のものをどうとるかということになります。対角線について対称になるようにするので、
対角線より上のところ、x<yな(x,y)をどう選ぶかです。(対角線の下で考えてもOK)そのような成分は全部でkC_2 個あります。このなかから、好きなものを好きなだけ取ってくればよいので、その取り方は2^{kC_2}通りです。ここで取ってきた成分(x,y)と、それをひっくり返した成分(y,x)と、最初にとった対角成分、全部足し合わせた集合が、反射的かつ対称的な関係になります。

Σ_{k=2 からnまで}nCk × 2^{kC_2} + n 

これが求める個数になるかと(空集合も二項関係としているなら、更に+1)。この式がもっと整理できるかはわかりません・・・ 
    • good
    • 1

表を書いて「ここは 1 にしないとダメだから~」とか「こことここは一緒にしないとダメだな~」とかやればわかる.


答えは 2^(n(n-1)/2) 個だ.
    • good
    • 3

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング