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