what is the expected number of collisions? Suppose we use a hash function $H$ to hash $N$ distinct balls into $M$ distinct bins. Assuming simple uniform hashing, what is the expected number of collisions?
Note that a collision is defined by adding a ball to an already occupied bin. If the already occupied bin has $k$ balls in it, then the number of collisions upon adding a new ball is $k.$

By using expectation, I tried as :
=> 1 × Probability of collision in first insertion  +
2 × Probability of collision in second insertion  + .......... +
n × Probability of collision in nth insertion
=> $(1 ∗ 0) + (2 ∗ 1/m) + (3 ∗ 2/m) + (4 ∗ 3/m) + … + (n ∗ n−1/m)$

Actually, The answer is $(n^2 - n)/2m$

But, I am not getting the answer. Where am I wrong here ?
 A: Note that if you end with $k$ occupied bins, then there were $N-k$ collisions. In other words, we want $N$ minus the expected number of occupied bins. This is easy - the probability a bin is unoccupied at the end is $\left(\frac{M-1}{M}\right)^N,$ so the expected number of unoccupied bins is this times $M$ and the expected number of occupied bins is $M\left(1-\left(\frac{M-1}{M}\right)^N\right),$ so our answer is $N$ minus this.
edit: this answers a different version of the problem. see paw's answer for the updated :)
A: The expected number of new collisions caused at the time of inserting the $k$-th ball is $\frac{k-1}{M}$ since it has a $\frac1M$ collision probability with each ball already placed.
Thus the expected number of collisions is
$\frac0M+\frac1M+\frac2M+\cdots+\frac{N-1}{M}=\frac{N(N-1)}{2}\cdot\frac1M$
A: you are claiming that $P(A \cap B)=P(A)+P(B)$, which is true iff the events are independent and they are not. Consider that when you insert 3rd element 
"Probability of collision in this insertion" = $1 \over m$ if there was a collision on 2nd insertion (2nd end up in the same bin as 1st) but it's $2 \over m$ is there was not, so $P_n$ depends on $P_1, \ldots ,P_{n-1}$ 
A: assuming @cats statment that "Collisions probably means the number of times you put a ball into an already occupied bin"
you can approach this by describing steps of the process and thinking about graph of states.
like: if while counting $c$ collisions so far and having  $i$ balls left there are $k$ empty bins left then with probability $p={1 \over k}$ you move to the state "$i-1$ balls ; $k-1$ empty bins; $c$ collisions" and with probability $1-p$ you move to state "$i-1$ balls; $k$ empty bins; $c+1$ collisions". 
In short:
Let $S(c,i,k)$ be state described above, the state graph looks like this:
$S(0,N,M)$ - start state
$S(c,0,k)$ - end stats (dla dowolnych $c,k$)
and the edges are:
$S(c,i,k)\begin{matrix}\overset{1 \over k}{\rightarrow} S(c,i-1,k-1)\\ \overset{k-1 \over k}{\rightarrow}S(c+1,i-1,k)\end{matrix} for\, i>0$
now Lets define $p_{cik}$ as probability of reaching state $S(c,i,k)$ and variable $\Bbb X$ which will be a number of collisions.
If we ask "from what state can i move into state $S(c,i-i,k-1)$", the answer will be "We where in $S(c,i,k)$ and we hit an empty bin or we where in $S(c-1,i,k-1)$ and we made a collision"
That gives us a recursive function:
$$p_{c\,i-1\,k-1}={1 \over k}p_{c-1\,i\,k}+{k-1 \over k}p_{c-1\,i\,k-1}$$
And additionally we can say:
$$p_{cik}=0\,for\,\begin{matrix}i \notin \{0,\dots,N\}\\ k \notin \{0,\dots,M\}\end{matrix}$$
since those are not possible
and that
$$p_{0NM}=1$$
that is enough to calculate $p_{cik}$ for $(i,k) \in \{0,\dots,N\} \times \{0,\dots,M\}$
Now we can say
$$P(\Bbb X=x)=\sum_{c_n,i,k} p_{c_nik}$$
where $0\le i \le N$ , $0\le k \le M$ , $\sum_nc_n=x$
Such model could be implemented in any programing language.
