I would like to derive the probability mass distribution $p_k$ of the number $k$ of fixed points of a random function from $A:=\{1,..,n\}$ to the same set.
-
I proceed computing the number of derangements $D_n$, as per a random permutation, obtaining:
$$ D_n = n^n – \binom n1 n^{n-1} + \binom n2 n^{n-2} – .. (-1)^k\binom nk n^{n-k}=\sum_{i=0}^n (-1)^i\binom ni n^{n-i}.$$ -
Then I compute the number of random functions with $k$ fixed points $n_k$ as the product of $\binom nk$ and $D_{n-k}$, as if to say that each function is composed by a $k$-subset of $A$ times a deranged $n-k$-disposition of the remaining $n-k$ elements of $A$:
$$n_k=\binom nk \sum_{i=0}^{n-k} (-1)^i\binom {n-k}i (n-k)^{n-k-i},$$ -
so that
$$p_k = \frac{n_k}{n^n}=\binom nk \sum_{i=0}^{n-k} (-1)^i\binom {n-k}i \frac{(n-k)^{n-k-i}}{n^n}.$$
To me it makes sense, but a quick check on Python shows me that $\sum_{k=0}^n p_k\neq 1$.
Any thoughts?
Best Answer
As JMoravitz pointed out in a comment, to find the number of functions with $\ k\ $ fixed points you need to multiply $\ {n\choose k}\ $ by the number of functions with no fixed points on $\ n-k\ $ elements—namely $\ (n-1)^{n-k}\ $—, not the number of derangements. Thus, \begin{align} p_k&=\frac{{n\choose k}(n-1)^{n-k}}{n^n}\\ &= {n\choose k} \left(\frac{1}{n}\right) ^k\left(1-\frac{1}{n}\right)^{n-k}\ . \end{align} That is, the distribution of the number of fixed points is $\ Binomial\big(n, \frac{1}{n}\big)\ $. Another way of seeing this is that each of the numbers $\ 1,2,\dots,n\ $ is independently and equally likely to be a fixed point with probability $\ \frac{1}{n}\ $.