東大の授業で奮闘するスレ

65：臺地 （qpPuO9q2）：2005/05/08(日) 12:09:14: >>56[1]
この問題ﾗﾒﾝ氏の担当だったのか・・・
すでに一年以上経過しているのが感慨深いですね（何

526 ：LAR-men （lBLdA0dk） ：2004/04/21(水) 19:23
19.　Aをm個、Bをn個の元からなる有限集合とするとき、AからBへの全射の総数
　　をS(m,n)で表すこととする。
　　
　　(a)　集合論的考察により、n^m=Σ[k=1,n]{C[n,k]*S(m,k)}を示せ。
　　(b)　(a)(および前問の公式)を用い、nに関する帰納法によって
　　　　　S(m,n)=Σ[k=0,n]{(-1)^(n-k)*C[n,k]*k^m}
　　　　を証明せよ。

　(a)　AからBへの写像の総数はn^mである。この総数を別の方法で数える。値域が
　　　Bのk個の元からなる部分集合となるものの個数はC[n,k]*S(m,k)に等しい
　　　から、m≧nのときは、これをk=1～nまで加えればよい。
　　　m<nのときは、k=1～mまで加えればよいが、k=1～nまで加えても、k>mのとき
　　　問題16.より、S(m,k)=0となるから、問題ない。

527 ：LAR-men （lBLdA0dk） ：2004/04/21(水) 20:56
(b)　n=1のとき、両辺とも1になる。
　　次に、j<nであるすべてのjについて問題の式を仮定すれば、(a)より、
　　S(m,n)=n^m-Σ[j=1,(n-1)]C[n,j]*S(m,j)
　　=n^m-Σ[j=1,(n-1)]<C[n,j]*Σ[k=0,j]{(-1)^(j-k)*C[j,k]*k^m}>
　　=n^m-Σ[k=0,(n-1)](<Σ[j=k,(n-1)]{(-1)^(j-k)*C[n,j]C[j,k]}>*k^m)
　　(これは実際書き出してみればわかると思います)
　　ここで、C[n,j]*C[j,k]=<n!/{j!(n-j)!}>*<j!/{k!(j-k)!}>=
　　<n!/{k!(n-k)!}>*<(n-k)!/{(j-k)!(n-j)!}>=C[n,k]*C[(n-k),(j-k)]より
　　S(m,n)=n^m-Σ[k=0,(n-1)]<C[n,k]*k^m*Σ[j=k,(n-1)]{(-1)^(j-k)*C[(n-k),(j-k)]}>
　　ここで、問題18.の最後の公式を用いれば、
　　Σ[j=k,(n-1)]{(-1)^(j-k)*C[(n-k),(j-k)]} (-1)^(n-k)=0だから
　　Σ[j=k,(n-1)]{(-1)^(j-k)*C[(n-k),(j-k)]}=(-1)^(n-k-1)
　　よって、S(m,n)=n^m-Σ[k=0,(n-1)]{C[n,k]*k^m*(-1)^(n-k-1)}
　　=n^m Σ[k=0,(n-1)]{C[n,k]*k^m*(-1)^(n-k)}
　　=Σ[k=0,n]{C[n,k]*k^m*(-1)^(n-k)}　(∵n^m=C[n,n]*n^m*(-1)^(n-n))
　　ゆえに、j=nのときも成立。

　　うーん、読みづらいですな・・・

※書き込む際の注意事項はこちら

※画像アップローダーはこちら

（画像を表示できるのは「画像リンクのサムネイル表示」がオンの掲示板に限ります）