Given n distinct objects, a set of all possible permutations of length 1-n are created. Then one of these permutations is chosen. I am trying to find out the expected length of this choice.
This is what I have currently:
From here, I am assuming that the sum of all permutations is $\lfloor en! – 1 \rfloor$.
When $p(i)$ is the probability of an arrangement having a length $i$ the expected length of the choice is
$$ E(i) = \sum_{i=1}^n i * p(l_I) $$
$$ = \sum_{i=1}^n i * \frac{P(n,i)}{\lfloor en! – 1 \rfloor} $$
My utimate objective is to create a plot of this expected value with varying parameter values. This ugly equation makes it very difficult. Am I doing this wrong ? Is there is better way to calculate this ?
Best Answer
Let $$f(n)=n!\sum_{k=0}^{n-1}\frac1{k!}$$ It is proved in the answer you linked that $$f(n)=\lfloor en!-1\rfloor$$ We want to compute $$\begin{align} g(n)&=\sum_{k=1}^nk\frac{n!}{(n-k)!}\\ &=n!\sum_{k=0}^{n-1}\frac{n-k}{k!}\\ &=n\cdot n!\sum_{k=0}^{n-1}\frac1{k!}-n!\sum_{k=1}^{n-1}\frac1{(k-1)!}\\ &=nf(n)-n(n-1)!\sum_{k=0}^{n-2}\frac1{k!}\\ &=nf(n)-nf(n-1)\\ &=n\left(\lfloor en!-1\rfloor-\lfloor e(n-1)!-1\rfloor\right) \end{align}$$
Dividing by $\lfloor en!-1\rfloor$ gives $$n-n\frac{\lfloor e(n-1)!-1\rfloor}{\lfloor en!-1\rfloor}\approx n-1$$ as the expected value.