Ta xét bài toán phụ: Cho $A = \{a_1,a_2,...,a_n\}$ và $B = \{b_1,b_2,...,b_n\}$. Đếm số song ánh $f: A\to B$ sao cho $f(a_i)\neq b_i,\forall i = \overline{1,n}$.
Bằng nguyên lí bao hàm loại trừ, dễ dàng chứng minh được kết quả của bài toán trên là: $\sum_{i=0}^n (-1)^i\frac{n!}{i!}$.
Như vậy, với mỗi $k=\overline{0,n}$ thì: $P_{n}(k) = \frac{n!}{k!}\sum_{i=0}^{n-k}\frac{(-1)^i}{i!}$.
Từ đây, dẫn đến: $\sum_{k=0}^n kP_n(k) = n!\sum_{k=1}^n\sum_{i=0}^{n-k}\frac{(-1)^i}{i!(k-1)!}$.
Ta chỉ cần chứng minh $\sum_{k=1}^n\sum_{i=0}^{n-k}\frac{(-1)^i}{i!(k-1)!} = 1$.
Rõ ràng tổng ở vế trái cũng chính là: $\sum_{k+i< n}\frac{(-1)^i}{i!k!}$.
Ta chứng minh $S_n = \sum_{k+i< n}\frac{(-1)^i}{i!k!}=1$ bằng phép quy nạp.
Khi $n=1$ thì đẳng thức đúng. Giả sử đẳng thức đúng với $n\in\mathbb N^*$.
Ta chứng minh đẳng thức đúng với $n+1$.
Dễ thấy: $S_{n+1} - S_n =\sum_{i+k = n}\frac{(-1)^i}{i!k!} = \frac{1}{n!}\sum_{i=0}^n(-1)^i\binom{n}{i}$.
Ta dễ dàng chứng minh được $\sum_{i=0}^n(-1)^i\binom{n}{i}=0$ bằng cách chứng minh số tập con có chẵn phần tử của $\{1;2;...;n\}$ là $2^{n-1}$.
Suy ra $S_{n+1} - S_n = 0$ hay $S_{n+1}=1$.
Theo nguyên lí quy nạp ta có $S_n=1,\forall n\in\mathbb N^*$.
Vậy $\sum_{k=0}^n kP_n(k) = n!$.