My friend gave me a problem, which can be reduced to the following.
Let $$$S(k)$$$ be the set of all arrays of size $$$n$$$ that contains $$$k$$$ ones and $$$n - k $$$ zeroes. Let for some array $$$s \in S(k)$$$ , $$$pos_s[1..k]$$$ denotes the position of those ones (say in increasing order, it doesn't matter actually). We have to calculate.
i.e, for all arrays $$$s \in S(k)$$$ we have to sum the positions of all $$$k$$$ ones.
My thoughts : Modification to binomial expansion? Noo. hmm, what about counting how many times each position occurs, but then there will be intersections, like I might put two ones at the same index, so ? what about inclusion-exclusion? No it's getting a lot messy.
Linearity of Expectation : Let's find the expected value of $$$ \sum_{i = 1}^{k} pos_s[i] $$$
Let's look at it it some other way. We choose random variables $$$X_{1, 2, .. k} $$$ lying in $$$[1, n]$$$ with same probability (Note that I'm not saying they're independent. ). Thus $$$E[X_i] = \frac{1 + 2 + .. n}{n} = \frac{n + 1}{2}$$$ Now by linearity of expectation,
.
Now, it's left to you to realise that
.
And since we've $$$n \choose k $$$ arrays possible, we deduce,
.
I went numb for a few seconds after completing the solution, I mean wtf, what about intersection, how can this be even possible, you can't just choose it randomly (I know the formal proof of LOE, but still :\ )
There are few things, that I know are true, but I can never digest them, "My favourite song has just 7 million views on youtube" is on second", "Linearity of expectation actually works" remains at first.
Maybe I overkilled it. Other easier solutions are welcome :)
The answer is a big sum like $$$(1 + 3 + 4) + (2 + 5) + \ldots $$$ where e.g. the first term denotes a sequence with ones at position 1, 3 and 4. You can easily count how many times each number will appear in this big sum and thus how many times it should be counted. I think about it as contribution to the answer. More in my blog.
Thanks, far easier this way.
hmm, what about counting how many times each position occurs, but then there will be intersections
No, there won't be. It just works fine.
Guess, who is good at overkill ?