数学 – 集合と写像 - 写像に関する諸概念(有限集合, 全射の総数, 階乗, 帰納法)

集合・位相入門
(岩波書店)
松坂 和夫 (著)

学習環境

• 数式入力ソフト(TeX, MathML): MathType
• MathML対応ブラウザ: Firefox、Safari
• MathML非対応ブラウザ(Internet Explorer, Google Chrome...)用JavaScript Library: MathJax

集合・位相入門(松坂 和夫(著)、岩波書店)の第1章(集合と写像)、4(写像に関する諸概念)、問題19-b.を解いてみる。

問題19-b.

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

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