Mean Number of Elements Fixed by Self-Map
Theorem
Let $n \in \Z_{>0}$ be a strictly positive integer.
Let $S$ be a finite set of cardinality $n$.
Let $S^S$ be the set of all mappings from $S$ to itself.
Let $\map \mu n$ denote the arithmetic mean of the number of fixed points of all the mappings in $S^S$.
Then:
- $\map \mu n = 1$
Proof
Let $f \in S^S$ be an arbitrary mapping from $S$ to itself.
Let $s \in S$ be an arbitrary element of $S$.
$s$ has an equal probability of being mapped to any element of $S$.
Hence the probability that $\map f s = s$ is equal to $\dfrac 1 n$.
There are $n$ elements of $S$.
By the above argument, each one has a probability of $\dfrac 1 n$ that it is a fixed point.
Thus the expectation of the number of fixed points is $n \times \dfrac 1 n = 1$.
$\blacksquare$
Examples
Example: $7$ Envelopes
$7$ letters are placed at random into $7$ addressed envelopes, not necessarily making sure that one envelope contains only one letter.
How many letters, on average, can be expected to be in its correct envelope?
Sources
- 1982: Donald J. Newman: A Problem Seminar: Expectations: $104$
- 1992: David Wells: Curious and Interesting Puzzles ... (previous) ... (next): The misaddressed letters: $131$