Hatena::Groupcsnagoya-sicp

クラなんとかの日記 このページをアンテナに追加 RSSフィード

2009-10-14

2.32

| 17:13 | 2.32 - クラなんとかの日記 を含むブックマーク はてなブックマーク - 2.32 - クラなんとかの日記 2.32 - クラなんとかの日記 のブックマークコメント

もっかい考えてみた.

n を集合のサイズとする.

n = 0 の場合(集合=S(0))

部分集合全体の集合ss(S(0))は,{()} の1つ.

n = 1 の場合(集合=S(1))

x_1 を要素とすると,部分集合全体の集合ss(S(1))は,{(), (x_1)} の2つ.

n = 2 の場合(集合=S(2))

x_2 を追加の要素とすると,ss(S(2)) = {(), (x_1), (x_2), (x_2, x_1)} の4つ

ss(S(2)) = {ss(S(1)), x_2 + ss(S(1))}

つまり,

n = k の場合,(集合=S(k))

ss(S(k)) = {ss(S(k-1)), x_k + ss(S(k-1))}

という関係が見てとれる.

つまり,新しい要素を含まない部分集合全体(ss(S(k-1)))と

新しい要素を含んでいる部分集合全体(x_k + ss(S(k-1))) の組合せがある.

こうやって見ると,常に部分集合の全体集合のサイズは,2^n となることもわかる.

(毎回二倍になるので.

ゲスト



トラックバック - http://csnagoya-sicp.g.hatena.ne.jp/clairvy/20091014