問題8891(友人問)
nを正整数、S={1,2,,,,,,,,,n} とする。Sの(空でもよい)部分集合A,B,C,Dで
A∪B∪C∪D=S かつ A∩B∩C=φをみたす集合の組(A,B,C,D)は何通りあるか。
解答
・わたしの…
A∪B∪C∪D=S かつ A∩B∩C=φ とは、ベン図で考えると…
A∩B∩C=D でないとありえない。
また、A,B,Cは少なくとも一つは異なるものがないと駄目。
so...n個のものを重複を許して3カ所に入れる場合から、3個とも入る場合を引けばいい…
つまり…1個の数字が3カ所に入るか入らないか…(2^3)^n
1個の数字が3個とも入るか…2^n
すべて入ってない場合はA∩B∩C={} になるから…1
けっきょく…
8^n-2^n+1 通り
でいいのかな…^^
↑
嘘っぱちだった…^^; Orz…
↓
・鍵コメT様からのヒントを頂いていました Orz〜
n=1のとき,すなわちS={1}のとき,A,B,C,DはどれもS,φのいずれかで,
(A,B,C,D)≠(φ,φ,φ,φ),(S,S,S,φ),(S,S,S,S)
であればよく,13通りあります.
*それでもピンと来ないままで…^^;;…
・友人からのもの
答:13^n
*これを読んでも重複のところがよくわからず…^^;
[別解]
Sの任意の数をiとする。
iのA,B,C,Dに属す、属さないのすべての組み合わせは 2^4通りある。
そのうち条件に合わない場合は i ∈ A∩B∩C∩D, i ∈ A∩B∩C かつ i ∉ D, i ∉ A, i ∉ B, かつ i ∉ C かつ i ∉ D の3通りだけである。
よって、条件を満たす場合は 2^4-3=13通り。
数 i は1,…,n の n個であるから、求める個数は 13^n である。
*こっちの方が少しわかりやすいわ ^^;v
ようは...任意の数 i に関して A∩B∩C=φ なのだから…
2^4 から、A,B,Cすべてに i があり、Dに i があるかどうかの2通りと、
A∩B∩C∩D=φの場合の1通りを引けばいいのでしたのね ^^;v