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?
 A: 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.
