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: Probability that a fixed element is a fixed point

Previous step Next step

In plain words

Among all $n!$ shuffles, the fraction that happen to send $i$ back to itself is just $1/n$ — by symmetry, each of the $n$ elements is equally likely to be $i$ 's image.

P(f(i)=i) = \frac{(n-1)!}{n!} = \frac{1}{n}, \qquad i=1,\ldots,n

Detailed analysis

Let $f$ be chosen uniformly at random among the $n!$ permutations of $\{1,\ldots,n\}$ . For a fixed $i$ , exactly $(n-1)!$ of the $n!$ permutations satisfy $f(i)=i$ (by the same count as before), so $P(f(i)=i) = (n-1)!/n! = 1/n$ .