0

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 ?

kgkmeekg
  • 197
  • Have you tried imitating the calculation at the linked question? It's very similar. – saulspatz Jun 13 '21 at 16:58
  • In the linked question, I understand the first part of the derivation. But I am afraid that I am quite clueless about how the Taylor's theorem is applied to get the final expression. – kgkmeekg Jun 13 '21 at 17:09

1 Answers1

2

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.

saulspatz
  • 53,131
  • Thanks. For future reference a better explanation of F(n) can be found here – kgkmeekg Jun 13 '21 at 18:11
  • 1
    @kgkmeekg Another explanation, anyway. Personally, I like the first one better, but that's a matter of personal taste, I think. – saulspatz Jun 13 '21 at 18:15
  • @saulpatz Unlike the second link, the first one contains a step jump which I am not really able to grasp. But I can see that regardless of that both expressions apply to your solution above. – kgkmeekg Jun 13 '21 at 18:26