I was trying to simply an expression in an exercise related to randomized algorithms. Here is the expression which I have obtained at the end.
$$ \displaystyle\frac{\displaystyle\sum_{i=1}^{n+k-1} i \binom{n-i}{k-1}}{ \displaystyle{n \choose k}}$$
Is there any way to simplify the numerator so that the whole expression simplifies into a nice closed formula? A combinatorial approach would be greatly appreciated.
Answer
Consider the number of ordered pairs $(a, S)$ such that $S$ is a $k$-element subset of $\{1,2, \dots, n\}$ and $a \le \min S$.
One way of counting:
Fix $\min S$.
If $\min S = i$, the number of sets = $\binom{n-i}{k-1}$ (choose $k-1$ from $\{i+1, i+2, \dots, n\}$. For each such $S$, you have $i$ possibilities for $a$.
Thus the number of $(a,S)$ pairs = $\sum_{i=1}^{n-k+1} i\binom{n-i}{k-1}$
Now count that differently: either $a = \min S$ or not.
If $a \neq \min S$, then the number is $\binom{n}{k+1}$ (pick $k+1$ elements basically)
If $a = \min S$, the number is $\binom{n}{k}$.
Thus the numerator you seek is $\binom{n}{k} + \binom{n}{k+1} = \binom{n+1}{k+1}$
So your expression simplifies to $\dfrac{n+1}{k+1}$.
(Note, I have assumed you wanted the sum upto $n-k+1$)
No comments:
Post a Comment