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: Combine both expressions for E[X]
Previous stepNext step
In plain words

Both routes computed the same average, so setting them equal finishes the proof with no further computation.

∑k=0nk⋅pn(k)=n!⋅E[X]=n!\sum_{k=0}^{n} k \cdot p_n(k) = n! \cdot \mathbb{E}[X] = n!
Detailed analysis

Equating the two expressions for E[X]\mathbb{E}[X] obtained in Steps 2 and 3 gives ∑k=0nk⋅pn(k)/n!=1\sum_{k=0}^n k\cdot p_n(k)/n! = 1, i.e. ∑k=0nk⋅pn(k)=n!\sum_{k=0}^n k\cdot p_n(k) = n!, which is exactly the identity to be proved.