MathLabs

Problem 1

Let pn(k)p_n(k) be the number of permutations of the set {1,…,n}\{1, \ldots, n\}, n≥1n \ge 1, that have exactly kk fixed points. Prove that ∑k=0nk⋅pn(k)=n!\sum_{k=0}^{n} k \cdot p_n(k) = n!. (A permutation ff of a set SS is a one-to-one mapping of SS onto itself; an element ii of SS is a fixed point of ff if f(i)=if(i) = i.)
Step 4 of 4: Match the two counts to conclude
Previous stepNext step
In plain words

Two honest ways of counting the same collection must give the same number — that's the whole proof.

∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k \cdot p_n(k) = n \cdot (n-1)! = n!
Detailed analysis

Steps 1 and 3 count the exact same set of pairs (f,i)(f,i) in two different ways, so the two expressions must be equal: ∑k=0nk⋅pn(k)=n⋅(n−1)!=n!\sum_{k=0}^{n} k\cdot p_n(k) = n\cdot(n-1)! = n!, as required.