There is n number of marbles in a bag, each marble has a number from 1 to n written on it; the marbles are drawn out of the bag one by one.
What is the chance that at least five marbles are drawn in the same order as their number? That is, what is the chance that there are five numbers $r,s,t,u,v$ such that $r$ is the $r$th marble drawn, $s$ is the $s$th marble drawn, ..., $v$ is the $v$th marble drawn?
Eg. if 7 marbles, one order that the marbles are drawn out in can be [1, 7, 3, 4, 5, 6, 2], where 1, 3, 4, 5, 6 have the same order as their number.
$\endgroup$ 31 Answer
$\begingroup$In the Robinson-Schensted correspondence between permutations and Young tableau, the length of the first row of the tableau corresponding to a permutation equals the length of the longest increasing subsequence of the permutation.
So, what you need to do is enumerate all standard Young tableau's whose first row has length less than $5$ (and subtract those from $n!$). You can use the hook-length formula to do that, but I'm not sure the calculations will be that easy.
There is quite a lot of literature on problems like these, involving longest increasing subsequences...
Edit: So, it seems you are asking a different question: How many permutations are there with at least $5$ fixed points... I will leave my answer above -for the references- and give an answer here for what you intended.
A derangement is a permutation with no fixed points. It is known that there are $\big[\frac{n!}{e}\big]$ derangements of $n$ elements (where $\big[ \ \big]$ is the nearest integer function, see wikipedia page linked earlier for proofs). Now, what we need is the number of permutations with $0,1,2,3$ or $4$ fixed points. Those would be about $$\binom{n}{0}\frac{n!}{e}+\binom{n}{1}\frac{(n-1)!}{e}+\binom{n}{2}\frac{(n-2)!}{e}+\binom{n}{3}\frac{(n-3)!}{e}+\binom{n}{4}\frac{(n-4)!}{e} $$
Divide that by $n!$ , you get about $\frac{1}{e}\big( 1+1+1/2+1/6+1/24 \big)$ probability to get less than $5$ fixed points. Subtract that from $1$ and your answer should be $$\frac{24e-65}{24e}$$
$\endgroup$ 4
