ここから本文です

離散数学の問題です。 n>=1である自然数nに対し、1からnまでの自然数の集合をS={...

アバター

ID非公開さん

2019/3/1912:42:37

離散数学の問題です。
n>=1である自然数nに対し、1からnまでの自然数の集合をS={1,2,...,n}で表す。

2^S上の2項関係で対称的なものは全部で何個存在するか。

という問題なのですが、答えが
2^((2^n (2^n +1))/2) となっています

どういうふうに考えればいいか教えてください。

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数:
51
回答数:
1
お礼:
250枚

違反報告

ベストアンサーに選ばれた回答

cli********さん

2019/3/1922:10:39

ID非公開さん

まず, S={1,2,3,…,n} 上での対称的な二項関係の個数を考えます.
理解しやすくするために, 具体的に, n=4 の場合で, 添付した画像を参考にしてください.

(ア) 1 にたいして, 2,3,4 との関係として, 矢印双方向が対称的であるとします.
(イ) 1 は自身にたいしての関係 (1,1) も対称的であることをみたします.
以上から
異なる x,y ∈S にたいしては, n(n-1)/2 個の関係が存在します.
(x,x) にたいしては n 個の関係が存在します.
すなわち, 選べる関係はこれらの和として
n(n-1)/2 + n = n(n+1)/2
となります.
それぞれが独立だから, 選択する場合の数としては
2^{n(n+1)/2}
となります.

すると
S 上の二項関係から 2^S 上の二項関係に変えた場合, n を 2^n に置きかえればよいでしょう.
したがって
2^{2^n(2^n+1)/2}
です.

ID非公開さん

まず, S={1,2,3,…,n} 上での対称的な二項関係の個数を考えます....

アバター

質問した人からのコメント

2019/3/23 00:36:18

図解までしていただき理解しやすかったです。
ありがとうございました!

あわせて知りたい

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる