離散数学が分からず困っています。

質問

集合Aの要素の個数を15とする。
Aの部分集合のうち、要素の個数が奇数である部分集合の個数はいくつか？

上の問題を解説して欲しいです。できれば分かりやすくお願いします。

回答No.4

Caper · ベストアンサー

● 答えは、(2 の 14乗)個 でしょうか … 。

● ところで、集合A の部分集合の総数が、空集合を含めて、(2 の 15乗)個 であることはおわかりですよね。15桁 の 2進数 によって、集合A の各部分集合のありようを表現できるからです。

● n は自然数であるとします。すなわち、n は 0 より大きい整数であるとします。
　 集合P の要素の数が n個 であるとき、集合P の部分集合の総数は (2 の n乗)個 です。それらの部分集合のうち、要素の数が奇数個のものは、総数の半分、すなわち (2 の (n - 1)乗)個 であると、私は思います。それにともない、それらの部分集合のうち、要素の数が偶数個のものも、総数の半分、すなわち (2 の (n - 1)乗)個 であると、私は思います。

● 数学的帰納法によって、私はそれを証明してみました。

　 n = 1 であるとき、

　 A = {a}
　 A の部分集合は、φ と {a} の 2個 です。すなわち、(2 の 1乗)個 です。
　 それらの部分集合のうち、要素の数が奇数個の部分集合は、{a} だけです。すなわち、(2 の (1 - 1)乗)個 です。

　 よって、n = 1 のときは、満たされます。

　 n = k のときに満たされるものと仮定します。このとき、b は A の要素ではないとします。A∪{b} は、要素の数が k + 1個 となります。
　 A の部分集合の総数は (2 の k乗)個 です。それらと、それらのおのおの部分集合に b を加えた集合が、A∪{b} の部分集合のすべてとなります ( 合計 (2 の (k + 1)乗)個 )。

　 仮定より、A の部分集合のうち、要素の数が奇数個の部分集合も、要素の数が偶数個の部分集合も、それぞれ (2 の (k - 1))個 です。それらのおのおのの部分集合に b を加えたとします。それまで要素の数が奇数個であった A の部分集合は、要素の数が偶数個の集合となり、それまで要素の数が偶数個であった A の部分集合は、要素の数が奇数個の集合となります。
　 b を加える前に要素の数が奇数であった A の部分集合 (2 の (k - 1)乗)個 と、b を加えた後に要素の数が奇数個となった集合 (2 の (k - 1)乗)個 との総数は、(2 の k乗)個 となります。

● あわてて証明を記述しましたので、わかりにくいものと思われます。ごめんなさい。
　 また、私はそこつ者です。以上の記述の中にあやまりが含まれている可能性は高いです。まちがっていましたら、ひらにごめんなさい。

回答No.3

ferien

ANo.1ANo.2です。集合の個数について

要素の個数が奇数である部分集合の個数は、
要素の個数が１個である集合、15Ｃ1＝１５個
要素の個数が３個である集合、15Ｃ3個
　　………
要素の個数が１５個である集合、15Ｃ15＝１個
で、
15Ｃ1＋15Ｃ3＋15Ｃ5＋……＋15Ｃ15
が求める集合の個数になると思います。

どうでしょうか？

回答No.2

ferien

ANo.1です。訂正です。済みません。
＞合計で８個あります。確認してみて下さい。
８個でなくて、８種類です。
個数はもっとあると思います。

回答No.1

ferien

集合Aの要素の個数を15とする。
＞Aの部分集合のうち、要素の個数が奇数である部分集合の個数はいくつか？
要素の個数が奇数である部分集合とは、
要素の個数が１個である集合、
要素の個数が３個である集合、
　　………
要素の個数が１５個である集合　

上のような集合の個数を求めること。

合計で８個あります。確認してみて下さい。