２項関係に対する問題

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

No.1 回答者： Tacosan 回答日時： 2009/07/02 10:14

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

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

No.2 回答者： settheory 回答日時： 2009/07/02 23:02

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

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

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

例えば、1だけ関係を持たせたいとしたら、Ｒ＝｛（1,1）｝とすれば、反射的かつ対称的です。
1と2にだけ関係を持たせたいとしたら、Ｒ＝｛(1,1) (2,2) (1,2) (2,1)｝とすれば良いです。

Ｓから、何か（自身を含む）と関係をもたせるものとして、ｋ個選んできます。（ｎＣｋ通り）

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

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

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

Σ_{k=2 からnまで}nＣk × 2^{kＣ_2} ＋ n　

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