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 3 of 4: Sum the count over all n choices of i

Previous step Next step

In plain words

There are $n$ possible elements to hold fixed, and each contributes the same count $(n-1)!$ , so simply multiply.

\#\{(f,i): f(i)=i\} = \sum_{i=1}^{n} (n-1)! = n \cdot (n-1)!

Detailed analysis

Summing the count from the previous step over every choice of $i \in \{1,\ldots,n\}$ gives the total number of pairs $(f,i)$ with $f(i)=i$ : $\sum_{i=1}^{n}(n-1)! = n\cdot(n-1)!$ .