部分集合

質問

部分集合の個数の問題です。

　「Aが3個の要素からなるとき、Aの部分集合は何個か」この場合は数が小さいので、｛１｝｛２｝｛３｝｛１，２｝というように、部分集合を一つ一つ数えてゆくとわかるのですが、要素の数が増えるとお手上げです。
　回答を見たところ、「各要素が部分集合に属すかどうかで、２＾3＝8通り」とありました。ということは、例えば要素が10個ならば、部分集合の数は２＾10通りということですよね・・・・・
　上記の「」内の回答をわかりやすくかみ砕いて貰えませんか。よろしくお願いします

回答No.1

adinat · ベストアンサー

要は2進数です。A={1,2,3}とします。そこで各桁ごとにその元が含まれている場合は1、含まれない場合は0を表す2進数を考えます。たとえば、こんな感じ。
{1,3}=101
{2}=010
{1,2,3}=111
φ=000
要するにA={1,2,3}の部分集合とは3桁の2進数全体と同じ数だけあるのです。だから2^3個。最後の事実が分かりにくければ、たとえば0000～9999までちょうど1万個=10^4個あるよね、ってのと同じ話です。

お礼

理解することが出来ました。本当に有難うございます。

回答No.2

pleiadescluster

組み合わせ(Combination)を考えれば良いと思います。
以下「C」はCombinationを表します。

要素が３個のとき，部分集合の数は，
空集合Φ・・・・・・・・・3C0
一つ{1},{2},{3}・・・・・3C1
二つ{1,2},{2,3},{1,3}・・3C2
三つ{1,2,2}・・・・・・・3C3
したがって，合計3C0+3C1+3C2+3C3です。

要素がn個のとき，部分集合の数fnは，
fn=Σ_k=0^n{nCk}=nC0+nC1+・・・+nCn

ここで，二項定理より
(a+b)^n=nC0a^n+nC1a^(n-1)b+nC2a^(n-2)b^2+・・・nCnb^n

a=1,b=1とすれば，
2^n=nC0+nC1+・・・+nCn

よって，要素n個の部分集合の数fnは，
fn=2^n

の数だけあります。

お礼

どうも有り難うございます。