FC2ブログ

Welcome to my blog

[答1407] 部分集合の決め方

ヤドカリ

ヤドカリ

P6200296.jpg



[答1407] 部分集合の決め方


 集合Uの要素が7個であるとき、次の条件に合うUの部分集合 A,B の決め方は何通り?

 (1) A≠B かつ A⊂B  (2) A≠B かつ A∩B≠Φ


[解答1]

 (1+x)n=1+n1x+n2x2n3x3+……+nn-1xn-1+xn です。

 一般化して集合Uの要素をn個とすれば、Uの部分集合は 2n 個です。

 Bの要素の個数がk個(k=1,2,3,……,n)であれば、nk 通りのBが考えられます。

 (1) AはBの部分集合で A=B が除かれるので、Aは 2k-1 通りで、

  A,Bのペアは nk(2n-1)=nk・2knk 通りあり、

  k=1,2,3,……,n として加えて、

  {(1+2)n-1}-{(1+1)n-1}=3n-2n 通りです。

 (2) A∩B は Φ を除いて、2k-1 通りが考えられ、

  A∩ は 2n-k 通りが考えられます。

  ただし、A∩B=B ,A∩=Φ であれば A=B だから適しません。

  A,Bのペアは nk{(2k-1)・2n-k-1}=(2n-1)nknn-k・2n-k

  k=1,2,3,……,n として加えて、

  (2n-1){(1+1)n-1}-{(1+2)n-2n}=(2n-1)2-3n+2n=4n-3n-2n+1 通りです。

 本問では n=7 のときですので、

 (1) 37-27=2187-128=2059 通り、

 (2) 47-27-37+1=16384-128-2187+1=14070 通りです。


[解答2]

 一般化して集合Uの要素をn個とすれば、Uの部分集合は 2n 個です。

 よって、A=B の場合は A=B=Φ を含めて 2n 通りあります。

 Uのそれぞれの要素 x について、

 (ab) x∈A∩B ,(a) x∈A∩ ,(b) x∈∩B ,(o) x∈A∪B の4通りあります。

 (1) A⊂B のとき、Uのそれぞれの要素について、

  (ab)(b)(o)の3通りだから、3n 通りあって、A=B となる 2n 通りを除いて、

  3n-2n 通りです。

 (2) Uのそれぞれの要素について、

  (ab)(a)(b)(o)の4通りだから、4n 通りあって、A=B となる 2n 通りを除いて、

  4n-2n 通りのうち、Uの要素全部が (a)(b)(o)である 3n 通りは条件に合いません。

  これを減じると A∩B=Φ を重ねて除くことになりますので、4n-2n-3n+1 通りです。

  また、条件に合わない A∩B=Φ の場合は、Uのそれぞれの要素について、

  (ab)(b)(o)の3通りだから、3n 通りあり、A=B=φ を除くと 3n-1 通り、

  一方、部分集合 2n 個のうち、異なる2個を A,B とする決め方は、2n(2n-1) 通りだから、

  A∩B≠Φ となるのは、2n(2n-1)-3n+1=4n-2n-3n+1 通りです。

 本問では n=7 のときですので、

 (1) 37-27=2187-128=2059 通り、

 (2) 47-27-37+1=16384-128-2187+1=14070 通りです。

.
スポンサーサイト



Comments 5

There are no comments yet.
-  
管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

-  
管理人のみ閲覧できます

このコメントは管理人のみ閲覧できます

スモークマン  
グーテンターク ^^

わたしは以下のようにしました...
(1)
c(7,1)*(2^1-1)+c(7,2)*(2^2-1)+c(7,3)*(2^3-1)+c(7,4)*(2^4-1)+c(7,5)*(2^5-1)+c(7,6)*(2^6-1)+c(7,7)*(2^7-1)
=2059

これは、[解答1]と同じですかね...^^

(2)
c(7,1)*(3^6-1)+c(7,2)*(3^5-1)+c(7,3)*(3^4-1)+c(7,4)*(3^3-1)+c(7,5)*(3^2-1)+c(7,6)*(3^1-1)
=14070

こっちも、同じかもしれませんが、(1)と同じ発想で...
A∩Bに7個のうち、1〜6個が含まれ、残り6〜1個が A,B,それ以外の3ヶ所に含まれるかどうかでプリミティブに計算...
一般式は求められなかったですが...^^;

ヤドカリ
ヤドカリ  
Re: タイトルなし

peachbozuさん、非公開コメントを有難うございます。
ご理解いただいたようで嬉しいです。

ヤドカリ
ヤドカリ  
Re: グーテンターク ^^

スモークマンさん、コメントを有難うございます。
[解答1]と同じ考え方ですが、[解答1]はまとめて計算しています。
後半は、[解答1][解答2]の合わせ技ですね。