Mean Number of Elements Fixed by Self-Map

From ProofWiki
Jump to navigation Jump to search


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$.


$\map \mu n = 1$


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$.



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?