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: Rewrite E[X] using the counts p_n(k)

Previous step Next step

In plain words

This is just the standard formula for the average of a random variable, written out using the counts $p_n(k)$ that the problem already provides.

\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot P(X=k) = \sum_{k=0}^{n} k \cdot \frac{p_n(k)}{n!}

Detailed analysis

On the other hand, by definition, $X=k$ for exactly $p_n(k)$ of the $n!$ equally likely permutations, so $P(X=k) = p_n(k)/n!$ , and the expectation of $X$ is $\mathbb{E}[X] = \sum_{k=0}^{n} k \cdot p_n(k)/n!$ .