黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

4.【高校数学IA】全体集合と部分集合を復習する(高校生3年生以上推奨)

数学 整数 集合と論理

プログラミングの為の高校数学を復習するコーナー。今回は全体集合と部分集合の知識をまとめていく。

画像処理やデータ分析の際にはクラスタリングといい、情報をある規則に沿って複数の部分集合に分けると言った時に集合の知識は役に立つであろう。

基本的な知識

集合について

集合とは、ある事柄の集まりのうち、定義が具体的に示されているものを指す。ここで以下のような図のように、集合Aに含まれる1〜5の整数をA={1,2,3,4,5}のように表す。


f:id:program_study:20140914011513p:plain:w600

ここでまた集合の要素xがAに属する事をx \in Aと書き、例えば1はAに含まれるので1 \in Aと書き、6はAに含まれないので6 \notin Aと表す。

部分集合について

集合Aが集合Bの部分集合であるとは、AがB の一部(あるいは全部)の要素だけからなることをを言う。このとき全ての要素xに対しx \in A \Rightarrow x \in Bが成立する事である。又集合Aが集合Bの部分集合である事をA \subseteqq Bと言う。


f:id:program_study:20140914011543p:plain:w600

例えば上の図でU=\{1,2,3,4,5\}で、P=\{1,3\}のときPの全ての要素yに対しy \in P \Rightarrow y \in Uとなるので、U \subseteqq Pが成立する。またUの部分集合のうちPを満たさない集合の事を補集合といい、\bar{P}と表す。このとき\bar{P}=\{2,4,5\}となる。

空集合(φ)について

空集合とは要素に何も含まない、要素数0の集合の事を言う。例えばAが空集合のときA = \phiと表す。以上より基本的な知識の説明は終了したので、早速問題に取りかかりたい。

問題(東京理科大学をかなり編集)

nを5以上の自然数とする。集合X=\{1,2,...,n\}の部分集合A,Bにおいて、
条件:任意のx \in Xに対して,x \in Aまたはx \notin Bを満たすものを考える。
このときAの要素の個数をaとし、Bの要素の個数をBとする。但し空集合の要素の個数は0とする。

(1):A=\{1,2,3,4\}であるとき、b=2であるようなBをすべて求めよ。
(2):b \leqq aである事を証明せよ。
(3):0 \leqq k \leqq nとしA=\{1,2,....,k\}とする。このときBは全部で何通りあるか?
(4):0 \leqq k \leqq nに対する整数kに対し、a = kとなるA,Bの組みは全部で何通りあるか?
(5):A,Bの組みは全部で何通りあるか?

解説

(1):すべてのx \in Xに対し、x \in Aまたはx \notin B  \Rightarrow x \in Aまたは\bar{B} よりBはAの部分集合である事が分かり、B \subseteqq A。このときb=2より、Aの中の要素のうち2つを選べば良くB=\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}(答)

ド•モルガンの法則もこういった感じで証明するが、高校卒業しないとやらない内容なため本問はちょっと早い。でも見ておいた方が良いので紹介する。
(2):背理法による。 b > aであると仮定すると、x \notin Aかつx \in Bであるx \in Xが存在する。ここでx \in Aまたはx \notin Bの否定がx \notin Aかつx \in Bである事を考えると、すべてのx \in Xに対して、x \in Aまたはx \in Bに矛盾する。以上よりb \leqq a

(3):Aの1〜kの要素をBに含めるかで2^k(通り)。尚これはAの直積集合の要素数を数えているのと同様である。

(4):まず集合XからAに含める要素の組み合わせで、{}_n\mathrm{C}_k 通り考えられる。次にk個の要素をBに含めるかで2^k通り考えられ、2^k*{}_n\mathrm{C}_k通り(答)。

(5):0個からk個までの場合を考えれば良い。ここからは2項定理を使って計算すると、\sum_{k=1}^{n} 2^k*{}_n\mathrm{C}_k  = (1+2)^n = 3^n(個)(答)