5
$\begingroup$

What will be the value of the following summation?

$$\sum_{i=1}^{m}{ \frac{i(n-i)!}{ n!} }$$

Is it $\frac{m}{2}$ ? Can anybody show the derivation?

  • 2
    $\frac m2$ is not correct for $n=1$ and I would expect the result to be dependent on $n$, too. Are you sure you typed your question correctly? Did you want to write $n$ instead of $m$?2012-07-17
  • 0
    The series becomes: $$\dfrac{1}{n} + \dfrac{2}{n(n - 1)} + \cdots + \dfrac{k}{n(n - 1)\cdots(n - k + 1)} + \cdots + \dfrac{m}{n(n - 1)\cdots(n - m + 1)}$$2012-07-17
  • 0
    Yes, the problem given is as follows: There is a string of length m chosen randomly from n characters. Before a character is added to the string, it is checked if the character is already present in a set S. If found, it declares the string non-unique, else it adds the character to the set S. What will be the length of the string that should be scanned on average? While trying to find the expected length, I came up with this expression and it has been mentioned that on average half the string length i.e. m/2 will be scanned.2012-07-17
  • 1
    WolframAlpha gives a closed form, and it is not very pretty: http://www.wolframalpha.com/input/?i=Sum%5Bi%28n-i%29%21%2Fn%21%2C+%7Bi%2C+1%2C+m%7D%5D (be sure to click "exact form")2012-07-18

1 Answers 1