数学 - 集合と位相 - 集合と写像 - 写像に関する諸概念(有限集合から有限集合への全射の総数について)

集合・位相入門

学習環境

• Surface 3 (4G LTE)、Surface 3 タイプ カバー、Surface ペン(端末)
• Windows 10 Pro (OS)
• 数式入力ソフト(TeX, MathML): MathType
• MathML対応ブラウザ: Firefox、Safari
• MathML非対応ブラウザ(Internet Explorer, Microsoft Edge, Google Chrome...)用JavaScript Library: MathJax
• 参考書籍
  • Pythonからはじめる数学入門
  • JavaScriptリファレンス 第6版
  • インタラクティブ・データビジュアライゼーション

集合・位相入門 (松坂 和夫(著)、岩波書店)の第1章(集合と写像)、4(写像に関する諸概念)、問題19を取り組んでみる。

19. 1. nのm乗はAからBへのすべての写像の個数。

       級数の各項は、Bのk個の元からなる部分集合への全射(fの終域をこの部分集合に制限した時)すべての個数。

       よって、右辺はAからBへの写像すべての集合の個数となる。

       以上の集合論的考察により、次のことが成り立つ。

       $n^m={\displaystyle \sum _{k=1}^n\left(\begin{array}{c}n\\ k\end{array}\right)}S\left(m,k\right)$

    2. n = 1のとき、(a)の等式は両辺とも1。

       $\begin{array}{l}S\left(m,n\right)\\ =n^m-{\left(n-1\right)}^m\\ =n^m-{\displaystyle \sum _{k=1}^{n-1}\left(\begin{array}{c}n\\ k\end{array}\right)S\left(m,k\right)}\\ =n^m-{\displaystyle \sum _{k=1}^{n-1}\left(\begin{array}{c}n\\ k\end{array}\right)\left({\displaystyle \sum _{j=0}^k{\left(-1\right)}^{k-j}\left(\begin{array}{c}k\\ j\end{array}\right)j^m}\right)}\\ =n^m-{\displaystyle \sum _{k=1}^{n-1}\left({\displaystyle \sum _{j=0}^k{\left(-1\right)}^{k-j}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}k\\ j\end{array}\right)j^m}\right)}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\left(\begin{array}{c}n\\ k\end{array}\right)\left(\begin{array}{c}k\\ j\end{array}\right)}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\frac{n!}{k!\left(n-k\right)!}·\frac{k!}{j!\left(k-j\right)!}}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\frac{n!}{j!\left(n-j\right)!}·\frac{\left(n-j\right)!}{\left(k-j\right)!\left(\left(n-j\right)-\left(k-j\right)\right)!}}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\left(\begin{array}{c}n\\ j\end{array}\right)\left(\begin{array}{c}n-j\\ k-j\end{array}\right)}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right)\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\left(\begin{array}{c}n-j\\ k-j\end{array}\right)}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right)\left({\displaystyle \sum _{k=j}^{n-1}{\left(-1\right)}^{k-j}\left(\begin{array}{c}n-j\\ k-j\end{array}\right)}\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right)\left({\displaystyle \sum _{k=j}^n{\left(-1\right)}^{k-j}\left(\begin{array}{c}n-j\\ k-j\end{array}\right)}-{\left(-1\right)}^{n-j}\left(\begin{array}{c}n-1\\ k-1\end{array}\right)\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right)\left(0-{\left(-1\right)}^{n-j}\left(\begin{array}{c}n-1\\ n-1\end{array}\right)\right)j^m}\\ =n^m-{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right){\left(-1\right)}^{n-j-1}{j}^m}\\ =\left(\begin{array}{c}n\\ n\end{array}\right){\left(-1\right)}^{n-n}{n}^m+{\displaystyle \sum _{j=0}^{n-1}\left(\begin{array}{c}n\\ j\end{array}\right){\left(-1\right)}^{n-j}{j}^m}\\ ={\displaystyle \sum _{j=0}^n\left(\begin{array}{c}n\\ j\end{array}\right){\left(-1\right)}^{n-j}{j}^m}\end{array}$

       以上から、帰納法により次のことが成り立つ。

       $S\left(m,n\right)={\displaystyle \sum _{k=0}^n\left(\begin{array}{c}n\\ k\end{array}\right){\left(-1\right)}^{n-k}{k}^m}$

       (証明終)