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: Linearity of expectation gives E[X] = 1

Previous step Next step

In plain words

Linearity of expectation lets us add up each element's individual chance of being fixed, even though the events are not independent.

X = \sum_{i=1}^{n} \mathbf{1}_{\{f(i)=i\}}, \qquad \mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n \cdot \frac{1}{n} = 1

Detailed analysis

Let $X$ denote the (random) number of fixed points of $f$ , so $X = \sum_{i=1}^n \mathbf{1}_{\{f(i)=i\}}$ , a sum of indicator variables. Linearity of expectation holds regardless of dependence between the indicators, so $\mathbb{E}[X] = \sum_{i=1}^{n} P(f(i)=i) = n\cdot\frac{1}{n} = 1$ .