# Finding $\sum\limits_{i=1}^m \frac{i(n-i)! }{ n!}$

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?

• $\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$? Jul 17 '12 at 8:27
• 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)}$$ Jul 17 '12 at 8:59
• 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. Jul 17 '12 at 15:35
• WolframAlpha gives a closed form, and it is not very pretty: wolframalpha.com/input/… (be sure to click "exact form") Jul 18 '12 at 0:57

I've voted to delete my original (non-) answer. Here's a real one. You're given a string $x=x_1x_2\dots x_m$ where each character $x_i$ is in a set of size $n$. Throughout, we assume $n\ge m$. (We can analyze the case where $n<m$ but it's messier.) The task is to determine whether $x$ has any duplicate characters. You've agreed that the algorithm to do this will use a set $S$, initially empty, and will test each character in turn, like this

for i = 1 to n
if x[i] is in S
quit: we've found a duplicate character
else
add x[i] to S
quit: no duplicates found


The question is, what is the expected value of the number of characters that have been inspected when the algorithm terminates? I'll give an example with $m=4$ before I give the general (and quite messy) value. Denote the expectation by $E(n,m)$.

($i=1$) The first iteration will simply result in $S=\{x_1\}.$

($i=2$) On the second iteration of the loop, $x_2$ will be in $S$ with probability $1/n$ and we'll quit, having inspected two characters, so we add the term $(2)(1/n)$ to our expectation. On the other hand, $x_2$ will not be in $S$ with probability $1-1/n = (n-1)/n$ so we add $x_2$ to $S$ and continue searching.

($i=3$) We get to the third iteration with probability $(n-1)/n$. We see that $x_3$ will be in $S$ with probability $2/n$ upon which we'll quit, having added the term $(3)(2/n)((n-1)/n)$ to our expectation. If $x_3$ is not in $S$, we'll continue with probability $((n-1)/n)((n-2)/n$.

($i=4$) In the last step, we have inspected all the characters in $x$ and will quit. This will add the final term, $(4)((n-1)/n)((n-2)/n)$ to our expectation.

Thus, we'll have $$E(n, 4)=(2)\frac{1}{n}+(3)\frac{2}{n}\cdot\frac{n-1}{n}+(4)\frac{n-1}{n}\cdot\frac{n-2}{n} = 4-\frac{4n-2}{n^2}$$ With a lot more tedious work, we can show that in general, with $n\ge m$ we'll have $$E(n, m) = \frac{1}{n^{m-3}}\sum_{k=1}^{m-3}\left(k(k+1)\prod_{j=1}^{k-1}(n-j)\right) +\frac{nm-m+2}{n^{m-2}}(n-1)\cdots (n-m+3)$$ As far as I can tell, there's no nice closed form for this. However, we do have a nice asymptotic estimate. I'm pretty sure that for fixed $m$, as $n$ gets large, $$E(n, m) \sim m - \binom{m}{3}\frac{1}{n}$$ This agrees with our intuition: for large $n$ almost all length-$m$ strings won't have duplicate characters, meaning that most strings will require inspecting all $m$ characters before we know whether or not there are any duplicates.