レス数が1スレッドの最大レス数(1000件)を超えています。残念ながら投稿することができません。
「集合・位相入門」輪読会
-
18. Bをn個の元からなる有限集合とする.Bのm個の元からなる部分集合の総数をnCmで表す.
もちろん(m>nならnCm=0.)0≦m≦nのとき
nCm=nPm/m!=n(n-1)…(n-m+1)/m!=n!/m!(n-m)!である.
またΣ[m=0,n]nCm=2^n.Σ[m=0,n](-1)^m*nCm=0.
解答 Bのm個の元からなる部分集合を1つ固定しCと名付ける.CからBへのすべての単射の集合を
Dとおく.Dの元の総数はnPmである.Dの元を1つ固定しfと名付ける.
E_f={g|gは値域がV(f)と一致するDの元}とするとEの元はCからV(f)への単射であるから
E_fの元の総数はmPm.D=∪[f∈D]E_fでf≠f'ならE_f∩E_f'=ΦだからnCm=nPm/mPm.
17.の結果を使えばnPm/m!=n(n-1)…(n-m+1)/m!.右辺の分母分子に(n-m)!をかければ
n(n-1)…(n-m+1)/m!=n!/m!(n-m)!.
上の結果はΣ[m=0,n]nCmがBのすべての部分集合の集合2^Bの元の総数を表している
ので2^nに等しい.
n≧1,1≦m≦nとする.n≧1だから∃b∈B.Bのm個の元からなる部分集合は,
B-{b}の(m-1)個の元からなる部分集合と{b}のユニオンか,B-{b}のm個の元からなる
部分集合のどちらかであり,そのどちらでもあることはない.したがって
nCm=(n-1)C(m-1)+(n-1)Cmである.
nが奇数のときはΣ[k=0,(n-1)/2]nC(2k)=Σ[k=0,(n-1)/2]nC(n-2k)=Σ[k=0,(n-1)/2]nC(2k+1).
nが偶数のときはΣ[k=0,n/2]nC(2k)=nC0+Σ[k=1,(n-2)/2]nC(2k)+nCn
=(n-1)C0+Σ[k=1,(n-2)/2]((n-1)C(2k-1)+(n-1)C(2k))+(n-1)C(n-1)
=Σ[k=0,n-1](n-1)Ck
=Σ[k=1,n/2]((n-1)C(2k-2)+(n-1)C(2k-1))
=Σ[k=1,n/2]nC(2k-1).
いずれにせよΣ[m=0,n](-1)^m*nCm=0.
掲示板管理者へ連絡
無料レンタル掲示板
