Skip to content

Limiting chance a random map has five fixed points

Question

Pick a function f:{1,…,n}→{1,…,n}f:\{1,\dots,n\}\to\{1,\dots,n\} uniformly at random from all nnn^n such functions, and let FnF_n count the points with f(i)=if(i)=i. The limit lim⁡n→∞P(Fn=5)\lim_{n\to\infty}\mathbb{P}(F_n=5) can be written as c/ec/e for a constant cc. What is cc?

Short answer

c=1120c=\tfrac1{120}. For a uniformly random function the values f(i)f(i) are independent, so each ii is fixed with probability 1n\tfrac1n independently and Fn∼Bin(n,1n)F_n\sim\text{Bin}(n,\tfrac1n). This converges to Poisson(1)\text{Poisson}(1), giving P(Fn=5)→e−15!=1120e\mathbb{P}(F_n=5)\to\tfrac{e^{-1}}{5!}=\tfrac{1}{120e}.

Adapted from QuantQuestions.io; question and answer rewritten by SelfMadeQuant.com.

See the hint and the full worked solution in the question bank (free account).

Open the worked solution

Lessons behind this question

Start with a free lesson: Probability Fundamentals is part of a free topic. Create a free account, no card needed, to read it in full with worked solutions.

Read it free