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 2 of 4: Count permutations fixing one chosen element

Previous step Next step

In plain words

Pin down where $i$ goes — namely, back to itself — and the rest of the permutation is free to do anything to the other $n-1$ elements.

\#\{f : f(i)=i\} = (n-1)! \quad \text{for each fixed } i \in \{1,\ldots,n\}

Detailed analysis

Fix an element $i \in \{1,\ldots,n\}$ . A permutation $f$ with $f(i)=i$ is completely determined by how it permutes the remaining $n-1$ elements $\{1,\ldots,n\}\setminus\{i\}$ among themselves, and every such rearrangement is allowed. Hence there are exactly $(n-1)!$ permutations of $\{1,\ldots,n\}$ that fix $i$ .