質問<1911>2004/9/1
①3個の異なる要素から成る集合について、 それぞれの長所と短所を明確にして解説せよ。 ②n個の異なる要素からなる集合の部分集合は、 いくつであると予想できるか。 ③②の予想が正しいことを証明せよ。 ★希望★完全解答★
お便り2004/9/1
from=wakky
集合の要素の長所・短所ってなんですか?
お便り2004/9/4
from=ゆうや
①3個の異なる要素から成る集合の部分集合の個数を 求めよ。 ②n個の異なる要素からなる集合の部分集合は、 いくつであると予想できるか。 ③②の予想が正しいことを証明せよ。 失礼しました。よろしくお願いします。
お便り2004/9/6
from=wakky
① 3個の要素を持つ集合を {A,B,C}とでもしましょう。 それぞれの要素を部分集合に入れることを○入れないことを×と表すこと にします。 つまり空集合={×××},{A}={○××}{A,C}={○×○} ということです。 そうするとどうでしょうか? ○と×を重複を許して3個並べる場合の数に等しくなりませんか? つまり2×2×2=8個となります。 ② これは容易に 2^nと予想できますね。 ③ どういうアプローチがいいのかなぁ? (その1) n個の要素からなる集合の部分集合の個数をS(n)とする。 S(n)=2^nを証明する。 要素が1個の場合は部分集合は空集合と全体集合しかないから2個で、 S(1)=2となり成り立つ。 n=kのとき成り立つと仮定する。 すなわちS(k)=2^kと仮定する。 要素の数がk+1の集合の場合、最初のk個だけでつくられる部分集合の数は 2^k個であり、そのそれぞれに対してk+1個目の要素が入るか入らないかの 2通りあるから、 S(k+1)=2^k×2=2S(k)=2^(k+1)となる。 よって、n=k+1のときも成り立つ。 こんなんでいいのかなぁ?それからS(0)=1を言っておいた方がいいかも しれません。 (その2) n個の要素からなる集合の部分集合の要素の数は、0からnまでの整数値をとる。 0≦k≦nである整数kに対して、要素の数がk個である部分集合の数は n個の中からk個を取り出す組み合わせに等しく、nCk個である。 したがって、部分集合の数は nC0+nC1+nC2+・・・+nCn である。 これは2項展開(1+1)^n そのものである。 つまり nC0+nC1+nC2+・・・+nCn=2^n こんな感じでいいんですかねぇ?