Problem 1

Let

p_n(k)

be the number of permutations of the set

\{1, \ldots, n\}

n \ge 1

, that have exactly

k

fixed points. Prove that

\sum_{k=0}^{n} k \cdot p_n(k) = n!

. (A permutation

f

of a set

S

is a one-to-one mapping of

S

onto itself; an element

i

S

is a fixed point of

f

f(i) = i

Step 1 of 4: Read the sum as counting fixed-point pairs

Previous step Next step

In plain words

Instead of grouping permutations by how many fixed points they have, just count, one at a time, every (permutation, fixed point) pair that exists — the total is the same, viewed from a different angle.

\sum_{k=0}^{n} k \cdot p_n(k) = \#\{(f,i) : f \text{ is a permutation of } \{1,\ldots,n\},\ f(i)=i\}

Detailed analysis

A permutation with exactly $k$ fixed points contributes exactly $k$ to the term $k \cdot p_n(k)$ , one for each of its fixed points. Summing over $k$ , $\sum_{k=0}^{n} k \cdot p_n(k)$ counts every pair $(f,i)$ where $f$ is a permutation of $\{1,\ldots,n\}$ and $i$ is a fixed point of $f$ , i.e. $f(i)=i$ .