2015年 大問3 (2)

院試で面白い問題があったのでメモ.

問題文

ある集合  A が与えられる.この  A の冪集合を  P(A) と表す.  P(A) 上の二項関係  R_{P(A)} を次のように定義する.

{
R_{P(A)} = \{ (a,b) \in P(A) \times P(A) | (a \subseteq b) \wedge (\forall c \in P(A))
[ ( (a \subseteq c) \wedge (c \subseteq b) ) \rightarrow ( (c=a) \vee (c=b) ) ] \}
}

 |A| = n の時, |R_{P(A)}| を求めよ.

方針

 n=2 の時で考えると,以下の図のような組み合わせが得られる.

f:id:t-tatsukawa:20170720015100j:plain

上の図から,今見ているグループと次のグループの積を足して, a=b となる要素を全て足したら答えが求まりそうに思える.

これは間違いである. |A|=3, A=\{0,1,2 \} で検証すると, \{ 2 \} \{ 0, 1 \} には推移しない.

しかしここから,次グループに推移する数を求めれば答えが求まりそうなことが分かる.

ではどのようにして考えればいいだろうか.

集合に含まれている  A の元を1, 含まれていない元を0としてビットで表現する.すると以下の図のような結果が得られる.

f:id:t-tatsukawa:20170720015743j:plain

よって次のグループに推移する数は  n-i 個ある.

解答

{ \displaystyle
2^{n} + \sum_{i=0}^{n-1} ((n-i)\cdot nC_i )
}

所感

いや,はてなブログmarkdown記法の数式の挙動が意味不明すぎて,組み合わせすら満足に書けないのは許してください. 本番でこれ解くなら  n=4 ぐらいまで実験しないと最初の方針で考えそうで怖い.

この性質を使えば何か問題できるかなぁ.