平成２６年５月１１日
[流れ星]
第305回数学的な応募解答
＜解答募集期間：４月13日～５月11日＞
［特殊な部分集合］
ｎ個の異なる要素からなる集合をSとする。Sの２つの部分集合の組（同じでもよい）で、その和集合がSになるようなものは何組あるか。次の問題に答えよ。
ただし、順番を変えただけのものは区別しないものとする。つまり、{１,２},{１,３,４}と,{１,３,４}、{１,２}は同じものとして数える。また、Sの部分集合の中には空集合も考える。また、ｎ＝１のときは{１}，{１}と{１}，φの2組と数えます。
問題１：ｎ＝２、３とき何組あるか数えてみてください。
問題２：一般の場合何組できるかｎで表してください。
NO1「uchinyan」
04/13 13時11分 受信 更新 05/11
例にあるように，S =
{1, 2, 3, ..., n} として一般性を失わないので，以下ではそうします。
問題１：
n = 1 の場合
S = {1}，部分集合，φ，{1}
φ と φ
---> NG
φ と {1}
---> OK
{1} と {1} ---> OK
2 組
n = 2 の場合
S = {1, 2}，部分集合，φ，{1}，{2}，{1, 2}
φ と φ
---> NG
φ と {1}
---> NG
φ と {2}
---> NG
φ と {1, 2}
---> OK
{1} と {1} ---> NG
{1} と {2} ---> OK
{1} と {1, 2} ---> OK
{2} と {2} ---> NG
{2} と {1, 2} ---> OK
{1, 2} と {1, 2} ---> OK
5 組
n = 3 の場合
S = {1, 2,
3}，部分集合，φ，{1}，{2}，{3}，{1, 2}，{1, 3}，{2, 3}，{1, 2, 3}
φ と φ
---> NG
φ と {1}
---> NG
φ と {2}
---> NG
φ と {3}
---> NG
φ と {1, 2}
---> NG
φ と {1, 3}
---> NG
φ と {2, 3}
---> NG
φ と {1, 2,
3} ---> OK
{1} と {1} ---> NG
{1} と {2} ---> NG
{1} と {3} ---> NG
{1} と {1, 2} ---> NG
{1} と {1, 3} ---> NG
{1} と {2, 3} ---> OK
{1} と {1, 2, 3} ---> OK
{2} と {2} ---> NG
{2} と {3} ---> NG
{2} と {1, 2} ---> NG
{2} と {1, 3} ---> OK
{2} と {2, 3} ---> NG
{2} と {1, 2, 3} ---> OK
{3} と {3} ---> NG
{3} と {1, 2} ---> OK
{3} と {1, 3} ---> NG
{3} と {2, 3} ---> NG
{3} と {1, 2, 3} ---> OK
{1, 2} と {1, 2} ---> NG
{1, 2} と {1, 3} ---> OK
{1, 2} と {2, 3} ---> OK
{1, 2} と {1, 2, 3} ---> OK
{1, 3} と {1, 3} ---> NG
{1, 3} と {2, 3} ---> OK
{1, 3} と {1, 2, 3} ---> OK
{2, 3} と {2, 3} ---> NG
{2, 3} と {1, 2, 3} ---> OK
{1, 2, 3} と {1, 2, 3} ---> OK
14 組
n = 3 の場合を見ると分かりますが，このようにして数えるのは不可能ではないもののなかなか大変です。
そこで，n = 3 の場合で，少し見方を変えて数えてみます。
A，B を S = {1, 2, 3} の部分集合とし，A∪B = S とすればいいので，
S の各要素を A と B に振り分ける，と考えます。
1 は A 又は B に存在すればいい，両方に存在してもいい，ので，その振り分け方は 2^2 - 1 = 3 通り。
2，3 も同様で 3 通りずつ。
そこで全体はこれらの積になりますが，A と B を入れ替えたものは同じとするので，
A = B かつ A∪B = S，つまり A = B =
S，以外は半分にする必要があります。
そこで，(3^3 +
1)/2 = 28/2 = 14 組，になります。
この考え方は一般化が容易です。
問題２：
問題１：の最後のように考えます。
A，B を S = {1, 2, 3, ..., n} の部分集合とし，A∪B = S とすればいいので，
S の各要素を A と B に振り分ける，と考えます。
1 は A 又は B に存在すればいい，両方に存在してもいい，ので，その振り分け方は 2^2 - 1 = 3 通り。
2，3，…，n も同様で 3 通りずつ。
そこで全体はこれらの積になりますが，A と B を入れ替えたものは同じとするので，
A = B かつ A∪B = S，つまり A = B =
S，以外は半分にする必要があります。
そこで，(3^n +
1)/2 組，になります。
(別解)
漸化式で考えます。
A，B を S = {1, 2, 3, ..., n} の部分集合で A∪B = S の場合を a(n) 通りとし，
この場合に n+1 を付け加えます。
付け加え方は，A に付け加える，B に付け加える，A と B の両方に付け加える，の 3 通りが可能ですが，
A = B かつ A∪B = S，つまり A = B =
S，のときだけは，片方だけに付け加えるのは重複してしまうので，
その分を引きます。そこで，
a(n+1) = 3
* a(n) - 1，a(1) = 2
です。これを解くと，
a(n+1) -
1/2 = 3(a(n) - 1/2)
a(n) - 1/2
= 3(a(n-1) - 1/2) = … = 3^(n-1) * (a(1) - 1/2) = 3^(n-1) *
(2 - 1/2) = 3^n/2
a(n) =
(3^n + 1)/2
そこで，(3^n +
1)/2 組，になります。
(感想)
最初，地道に調べていくと，入れ替えて同じものを除くのがややこしそうで，
どうしたものか，と思ったのですが，ふと，問題１：の最後の考え方を思い付き，
なんだそうか，という感じでした (^^;
漸化式は確認という感じで追加しました。
NO2「ｽﾓｰｸﾏﾝ」
04/14 20時04分 受信 更新 05/11
今回も面白そうでチャレンジ☆
問題１：ｎ＝２、３とき何組あるか数えてみてください。
n=2 のとき…
(1,2)-(1,2),(0)
(1,2)-(1)
(1,2)-(2)
(1)-(2)
つまり…5組
n=3 のとき…
(123)-(123), (0)
(123)-(1),(2),(3)
(123)-(12),(23),(13)
(12)-(23)
(12)-(13)
(13)-(23)
(12)-(3)
(13)-(2)
(23)-(1)
(1)-(1),(1)-(0)
(12)-(12),(12)-(1)
(12)-(0),(12)-(2)
(1)-(2)
つまり…14組
問題２：一般の場合何組できるかｎで表してください。
構造的には…両方同じなら2倍に増え、残りは3倍増える…
そのとき、両方同じ組は常に1組なので…
f(1)=2
f(2)=2*1+3*(f(1)-1)
f(3)=2*1+3*(f(2)-1)
f(k)=3*f(k-1)-1
f(k)-a=3*(f(k-1)-a)
2a=1
f(k)-1/2=3*(f(k-1)-1/2)
つまり…
f(n)-1/2=3^(n-1)*(f(1)-1/2)=3^(n-1)(3/2)
f(n)=(3*3^(n-1)+1)/2
でよさそうですね♪
NO3「二度漬け白菜」 04/16 00時53分 受信 更新 05/11
問題1:
n=2のとき、5組 (答)
{φ,{1,2}}, {{1},{2}}, {{1},{1,2}}, {{2},{1,2}},
{{1,2},{1,2}}.
n=3のとき、14組 (答)
{φ,{1,2,3}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}},
{{1},{1,2,3}},
{{2},{1,2,3}}, {{3},{1,2,3}}, {{1,2},{1,3}},
{{1,2},{2,3}}, {{1,3},{2,3}},
{{1,2},{1,2,3}}, {{1,3},{1,2,3}}, {{2,3},{1,2,3}},
{{1,2,3},{1,2,3}}.
問題2:
一般化して考えてみます。
n,mを正整数とします。
n 個の異なる要素からなる集合をSとします。
Sの m 個の部分集合の組(同じものがあってもよい)で、その和集合がSになるようなものの組の総数をA(n,m)とします。
ただし、順番を変えただけのものは区別しないものとし、またSの部分集合の中には空集合も考えるものとします。
A(n,m)を求めます。
Sのn個の要素のうち、特定のk個の要素を含まないようなSの部分集合は全部で2^(n-k)個あります。
この2^(n-k)個の部分集合の中から、重複を許してm個の部分集合を取り出す方法は、
comb(2^(n-k)+m-1,m)通りあります。
また特定のk個の要素の選びかたは、comb(n,k)通りあります。
包除原理を使えば、A(n,m)の式は次のようになります。
A(n,m)=Σ[k=0～n]((-1)^k)*comb(n,k)*comb(2^(n-k)+m-1,m)
=(1/m!)*Σ[p=0～m]Σ[h=0～m-p]Σ[j=0～h]((2^(p*n))*((1-1/(2^p))^n)*((-1)^(m+p+j+h))*comb(h,j)*comb(m-1+h,m-p+h)*comb(2*m-p,m-p-h)*(h-j)^(m-p+h))/h!
mの値を具体的に与えれば、A(n,m)は n だけの式になります。
m=1,2,3,…,10 に対する
A(n,m)の式は次のようになりました。
A(n,1)=1,
A(n,2)=(3^n + 1)/2,
A(n,3)=(7^n+3^(n+1)+2)/6,
A(n,4)=(6*7^n+15^n+11*3^n+6)/24,
A(n,5)=(31^n+5*7^(n+1)+2*3^n*5^(n+1)+50*3^n+24)/120,
A(n,6)=(15*31^n+7^n*(3^(2*n)+225)+17*3^n*5^(n+1)+274*3^n+120)/720,
A(n,7)=(127^n+175*31^n+7^(n+1)*(3^(2*n+1)+232)+49*15^(n+1)+196*3^(n+2)+720)/5040,
A(n,8)=(28*127^n+1960*31^n+255^n+7^(n+1)*(46*3^(2*n)+1876)+6769*15^n+484*3^(n+3)+5040)/40320,
A(n,9)=(546*127^n+511^n+22449*31^n+4*3^(n+2)*85^n+7^n*(56*3^(2*(n+2))+118124)+2492*3^(n+3)*5^n+12176*3^(n+2)+40320)/362880,
A(n,10)=(9450*127^n+45*511^n+31^n*(33^n+269325)+58*15^(n+1)*17^n+7^n*(21091*3^(2*n+1)+1172700)+144736*3^n*5^(n+1)+114064*3^(n+2)+362880)/3628800.
NO4「浜田明巳」
04/17 12183分 受信 更新 05/11
最初に問題２を解く．
１～ｎのｎ個の数を，Ｐ，Ｑの２つのグループに分ける．
１は，Ｐのみに入るか，Ｑのみに入るか，Ｐ，Ｑの両方に入るかの３通り．
２～ｎも同様に３通り．
故に全部で，重複を含めて３ｎ通りある．
１～ｎがすべてＰ，Ｑの両方に入る場合以外は重複しているので，場合の数は，
(３ｎ－１)／２＋１通り
これはｎ＝１のとき，２通りとなり，例の答と合う．
次に問題１について．
ｎ＝２のとき，(３２－１)／２＋１＝５（通り）
ｎ＝３のとき，(３３－１)／２＋１＝１４（通り）
エクセルのマクロで検証してみた．これによると，
ｎ＝１のとき，２
ｎ＝２のとき，５
ｎ＝３のとき，１４
ｎ＝４のとき，４１＝(３４－１)／２＋１
ｎ＝５のとき，１２２＝(３５－１)／２＋１
ｎ＝６のとき，３６５＝(３６－１)／２＋１
ｎ＝７のとき，１０９４＝(３７－１)／２＋１
ｎ＝８のとき，３２８１＝(３８－１)／２＋１
となり，実際の場合と合う．
（マクロ）
Option Explicit
Const nmax As Integer = 8
Dim a(nmax) As Integer, n As Integer
Sub Macro1()
For n = 1 To nmax
Cells(1, 4 * n - 3).Value = n: Cells(2, 4
* n - 3).Value = 0
Columns(retsu(4 * n - 2) &
":" & retsu(4 * n - 1)).Select
ActiveWindow.SmallScroll ToRight:=1
Selection.NumberFormatLocal =
"@"
Call saiki(1)
If n >= 5 Then
Columns(retsu(4 * n - 2) &
":" & retsu(4 * n - 2)).Select
Columns(retsu(4 * n - 2) &
":" & retsu(4 * n - 1)).EntireColumn.AutoFit
End If
Next n
End Sub
Sub saiki(ByVal m As Integer)
Dim P As String, Q As String
Dim deta As Integer, j As Integer
a(m) = 1 '1:P, 2:Q, 3:PQ
While a(m) <= 3
If m < n Then
Call saiki(m + 1)
Else
P = "": Q =
""
For j = 1 To n
Select Case a(j)
Case
1: P = P + Str(j)
Case
2: Q = Q + Str(j)
Case
Else: P = P + Str(j): Q = Q + Str(j)
End Select
Next j
deta = 0: j = 1
While deta = 0 And j <=
Cells(2, 4 * n - 3).Value
If (P = Cells(j, 4
* n - 2).Value And Q = Cells(j, 4 * n - 1).Value) Or (P = Cells(j, 4 * n -
1).Value And Q = Cells(j, 4 * n - 2).Value) Then
deta =
1
Else
j = j
+ 1
End If
Wend
If deta = 0 Then
Cells(2, 4 * n -
3).Value = Cells(2, 4 * n - 3).Value + 1
Cells(Cells(2, 4 *
n - 3).Value, 4 * n - 2).Value = P
Cells(Cells(2, 4 *
n - 3).Value, 4 * n - 1).Value = Q
End If
End If
a(m) = a(m) + 1
Wend
End Sub
Private Function retsu(ByVal m As Integer) As String
retsu = ActiveSheet.Cells(1, m).Address(False, False)
retsu = Left(retsu, Len(retsu) - 1)
End Function
NO5「早起きのおじさん」
04/18 09時03分 受信 更新 05/11
第305回解答 早起きのおじさん
●あらかじめあとで使う式を確認しておきます。
・
これは、要素がｎ個の集合の部分集合の個数を考えると分かりやすいと思います。
部分集合は要素の個数が0個からn個のものまであります。
1個1個の要素からみると、部分集合の要素になるかならないかのどちらかです。
・
特に、ｘ＝2のときは、
となります。
これは、二項定理から簡単に確認できます。
問題1
Ｓ2＝｛1,2｝の部分集合の個数は、22＝4です。
Ｓ3＝｛1,2,3｝の部分集合の個数は、23＝8です。
便宜上空集合φを0、｛1,2｝を12などと表すことにします。
次の表より、ｎ＝2のときは5組、ｎ＝3のときは14組あります。
灰色の部分は、対称性から左下と同じなので数えません。
問題2
ｎ＝4（Ｓ4＝｛1,2,3,4｝）のときを調べることで、一般の場合の手がかりにします。
はじめは、対称性を無視して、とにかく和集合が全体集合Ｓ4になるものを調べます。
表の左下の部分を数えると答えは、41組です。
対称の中心（黄色の部分）にあるのは1組だけです。
考え方としては、表全体の組数に1を加えて半分にします。
●さて、例えば表の上からⅣ段目の部分を見てみます。
元の集合の要素の個数が4なので、要素が3つの部分集合は、4Ｃ3＝4個あります。
｛1,2,3｝、｛1,2,4｝、｛1,3,4｝、｛2,3,4｝
・左からＢ番目のところに該当する組が4あります。
これらは、互いに補集合の関係にあるもののペアです。
｛1,2,3｝と｛4｝、 ｛1,2,4｝と｛3｝、 ｛1,3,4｝と｛2｝、 ｛2,3,4｝と｛1｝
4×1＝4Ｃ3×3Ｃ0と考えます。(3Ｃ0は、余分に要素を取らないという意味です)
・左からＣ番目のところに該当する組が12あります。
例えば、｛1,2,3｝と組むことができるのは、4と残り1,2,3の中から1つだけ選んだ要素からできる部分集合です。
このように考えて、
｛1,2,3｝と｛1,4｝か｛2,4｝か｛3,4｝、 ｛1,2,4｝と｛1,3｝か｛2,3｝か｛3,4｝、
｛1,3,4｝と｛1,2｝か｛2,3｝か｛2,4｝、 ｛2,3,4｝と｛1,2｝か｛1,3｝か｛1,4｝
12＝4×3＝4Ｃ3×3Ｃ1と考えます。
・左からＤ番目のところに該当する組が12あります。
例えば、｛1,2,3｝と組むことができるのは、4と残り1,2,3の中から2つだけ選んだ要素からできる部分集合です。
このように考えて、
｛1,2,3｝と｛1,2,4｝か｛1,3,4｝か｛2,3,4｝、 ｛1,2,4｝と｛1,2,3｝か｛1,3,4｝か｛2,3,4｝、
｛1,3,4｝と｛1,2,3｝か｛1,2,4｝か｛2,3,4｝、 ｛2,3,4｝と｛1,2,3｝か｛1,2,4｝か｛1,3,4｝
12＝4×3＝4Ｃ3×3Ｃ2と考えます。
・左からＥ番目のところに該当する組が4あります。
例えば、｛1,2,3｝と組むことができるのは、4と残り1,2,3の中から3つだけ選んだ要素からできる部分集合です。
このように考えて、
｛1,2,3｝と｛1,2,3,4｝、 ｛1,2,4｝と｛1,2,3,4｝、
｛1,3,4｝と｛1,2,3,4｝、 ｛2,3,4｝と｛1,2,3,4｝
4＝4×1＝4Ｃ3×3Ｃ3と考えます。
・以上からⅣ段目の合計は、
4＋12＋12＋4＝4×1＋4×3＋4×3＋4×1＝4×(1＋3＋3＋1)＝4Ｃ3×(3Ｃ0＋3Ｃ1＋3Ｃ2＋3Ｃ3)
と考えます。
●このようにⅠ段目から考えていくと、
・Ⅰ段目は、4Ｃ0×0Ｃ0
・Ⅱ段目は、4Ｃ1×(1Ｃ0＋1Ｃ1)
・Ⅲ段目は、4Ｃ2×(2Ｃ0＋2Ｃ1＋2Ｃ2)
・Ⅳ段目は、4Ｃ3×(3Ｃ0＋3Ｃ1＋3Ｃ2＋3Ｃ3)
・Ⅴ段目は、4Ｃ4×(4Ｃ0＋4Ｃ1＋4Ｃ2＋4Ｃ3＋4Ｃ4)
●以上をまとめると、
4Ｃ0×0Ｃ0＋4Ｃ1×(1Ｃ0＋1Ｃ1)＋4Ｃ2×(2Ｃ0＋2Ｃ1＋2Ｃ2)
＋4Ｃ3×(3Ｃ0＋3Ｃ1＋3Ｃ2＋3Ｃ3)＋4Ｃ4×(4Ｃ0＋4Ｃ1＋4Ｃ2＋4Ｃ3＋4Ｃ4)
＝
以上から、ｎ＝4のときは、
組です。
●この考え方をｎ個の場合にあてはめると、
となります。
「早起きのおじさん」 04/27 08時10分 受信 更新 05/11
第305回解答（その２）
●この考え方は、要素がｎ個の集合の部分集合の個数の数え方と似ています。
部分集合は要素の個数が0個からn個のものまであります。
1個1個の要素からみると、部分集合の要素になるかならないかのどちらかです。
●Ｓの2つの部分集合をA、Bとします。
和集合
がＳになるということは、要素sからみると、
(1)
（ｓはBではない） (2)
（ｓはAではない） (3)
の3つのどれかがなりたつということです
・
のときは、内容的には同じペアが2組考えられます。
（AとB）は（BとA）と同じです。
中身が同じものは区別しません。
・
のときは、1組しかありません。
考え方としては、全体の組数に1を加えて半分にします。
●この考え方をｎ個の場合にあてはめると、
となります。
「早起きのおじさん」 04/28 21時01分 受信
更新 05/11
第305回解答（その３） ●漸化式を用いて考えます。
ｎ個の異なる要素からなる集合をＳnとし、Ｓnの2つの部分集合の組で、その和集合がＳnになるようなものの組数をanとします。
a1＝2です。（問1の解より、a2＝5、a3＝14です）
●Ｓnの場合の組の一方を便宜的にＡグループ、もう一方をＢグループとします。（どちらをＡ、Ｂにするかは任意でかまいません）
Ｓn+1の場合をＳnのときの組をもとにして考えます。
Ｓn+1の組は、次の手続きのどれかになります。
(1)ＳnのときのＡグループの要素に｛n+1｝を付け加えたもの
(2)ＳnのときのＢグループの要素に｛n+1｝を付け加えたもの
(3)ＳnのときのＡ、Ｂ両方のグループの要素に｛n+1｝を付け加えたもの
・Ｓnの組に｛n+1｝を付け加えるので、この手続きのあと組として同じになるものは次の1組だけです。
Ａ、Ｂグループとも元の集合Ｓnのときだけ(1)と(2)の手続き後、組として同じになります。(だぶりは1組だけです)
・Ｓnの場合の組にもれがなければ、Ｓn+1の組にも、もれはありません。
Ｓn+1の組にもれがあったとします。
もれた組の要素を書き出します。
次に、これらの要素から｛n+1｝を取り除いてみます。
そうするとＳnの組となります。
するとＳnの組のリストにもれがないのだから、すでにあるリストのどれかと一致することになります。
これはもれがあるとしたことに矛盾があるのでＳn+1の組にも、もれがないことになります。
●よって、次の漸化式が成り立ちます。
特性方程式 
の解
を用いて、
よって
は、初項
、公比3の等比数列となります。
∴
NO6「にいばりZ12」 05/03 00時03分 受信 更新 05/11
問題1
|
ｎ＝２の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
空集合φ＝｛｝に対してはすべての元が対応し |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
S∪φ =Sから、｛1,2｝のみです。・・・１個 ① |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
空集合を1組の一方の集合と考えると上記１組だけをカウントすればよいことになります |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2｝｛1,2｝・・・2個 ②-1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛2｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛1,2｝・・・2個 ②-2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1,2｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
φ｛1｝｛2｝｛1,2｝・・・4個 ③ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
ここで、②-1.2のダブりが、｛1｝｛2｝の1個 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
③が①②とダブるのはφ｛1,2｝、｛1｝｛1,2｝、｛2｝｛1,2｝の3個 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
よって1+2+2+4-1-3＝5個・・・・回答 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
列挙すると |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
φ｛1,2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛1,2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2｝｛1,2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2｝｛1,2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
となります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
ｎ＝3の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
空集合φ＝｛｝に対してはすべての元が対応し |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
S∪φ =Sから、｛1,2,3｝のみです。・・・１個 ①-1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2,3｝｛1,2,3｝・・・2個 ②-1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛2｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,3｝｛1,2,3｝・・・2個 ②-2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛3｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2｝｛1,2,3｝・・・2個 ②-3 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1,2｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛3｝｛2,3｝｛1,3｝｛1,2,3｝・・・4個 ③-1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1,3｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2｝｛1,2｝｛2,3｝｛1,2,3｝・・・4個 ③-2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛2,3｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛1,2｝｛1,3｝｛1,2,3｝・・・4個 ③-3 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次に部分集合｛1,2,3｝について考えると和集合がSとなるのは |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
φ｛1｝｛2｝｛3｝｛1,2｝｛1,3｝｛2,3｝｛1,2,3｝・・・8個 ④ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
ここで、②と③のダブりが、｛1｝｛2,3｝、｛2｝｛1,3｝、｛3｝｛1,2｝、｛1,2｝｛2,3｝、｛1,2｝｛1,3｝、｛1,3｝｛2,3｝、の6個 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
④が①②③とダブるのは｛1,2,3｝｛1,2,3｝以外のの7個 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
よって1+2+2+2+4+4+4+8-6-7＝14個・・・・回答 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
列挙すると |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
φ｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2｝｛1,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛3｝｛1,2｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛3｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2｝｛1,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2｝｛2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,3｝｛2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,3｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛2,3｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
｛1,2,3｝｛1,2,3｝ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
となります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
問題2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
n個の元を考える場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
第１組を集合Ｉとし、その補集合をＩ’とします |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
第２組を集合Pとしその補集合をP’とします |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
第1組と第2組の積集合をKとします（K=I∩P） |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
S=P'∪K∪I' P'∩K=φ K∩I'=φ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
I=K∪P' |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P=K∪I' |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
これらを踏まえると集合Iと集合Pは同等（可換）であるためIが取りうる集合はすべてPも取りうる事が解ります。・・・・（A) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの場合の数を計算します |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの場合の個数・・・・・② |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kを選ぶ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの元が0個の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nC0=1 K=φ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの元が１個の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nC1=n |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの元が2個の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nC2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの元がi個の場合 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nCi |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの元がn個の場合（K'=φ) |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nCn=1 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
足し合わせると |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Km=Σi=0→n nCi |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
次の３個の集合を考えます |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P’、K、I’ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kがi個の元を持つ場合のKの元が取りうる場合の数は上記から |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
nCi |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
一方で、この時P’はn-i個のKと異なる元を持ちうるので |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P’の持ちうる元の個数はn-i個 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P'がn-i個の元を持つ場合のP'の元が取りうる場合の数(φを含む)は |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P'mi=Σj=0→n-i n-iCj |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
以上からP'の取りうる場合の数は |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P'mｊi=Σj=0→n-i i=0→n n-iCj・nCi |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
となります |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
また、 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
P'mi=Σj=0→n-i n-iCj |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
は二項係数の総和に等しいので |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
（1+1）n-i＝2n-i に等しい |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
よって |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
上式中nCiもまた2項係数なので |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
この式は、（2+1）ｎ＝3ｎ |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
と書くことができます |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
ここで、（A）から、I'とP'を入れ替えたものを１つとしてカウントするという条件を考えます |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Kの集合に対応するP'の集合は（A)からI'にも存在し場合の数は1/2 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
になります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
ただし、K＝Sの場合にのみP'=I'=φとなり場合の数が1となります。 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
したがって求める組み合わせの数をSmとすると |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Sm=（3n+1）/2・・・・回答 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。
