A probability problem I am stuck on

Question

A cell contains $N$ chromosomes, between any two of which an interchange of parts may occur. If $r$ interchanges occur then what is the probability that exactly $m$ chromosomes were involved? The answer is given to be $$\dbinom{N}{m}\dbinom{N}{2}^{-r}\sum_{k=2}^{m}(-1)^{m-k}\dbinom{m}{k}\dbinom{k}{2}^r$$ I was approaching the problem like this : First let us choose two of them in $\dbinom{m}{2}$ ways and they can interchange in $\dbinom{2}{2}^r=1$ ways. Then there will be some overcounting and we will need to subtract $\dbinom{m}{3}\dbinom{3}{2}^r$ and so on. But there is some problem. I don't get the $(-1)^{m-k}$ part. I think we might need inclusion and exclusion but nothing works out. I don't understand what should be the events I would apply Inclusion Exclusion Principle on? Or maybe there's some other way? Anyways, any help would be appreciated. Thanks.

Answer 1

Substituting $k$ by $m-k$ in the sum above and using that $\binom{m}{k}=\binom{m}{m-k}$, the given probability, which from now we will call $p$, can equivalently be expressed as $$p = \binom{N}{m} \binom{N}{2}^{-r} \sum_{k=0}^{m-2} (-1)^{k} \binom{m}{k} \binom{m-k}{2}^r.$$ Note that the above formula can only be valid if $m \leq 2r$ because there can at most be $2r$ chromosomes involved in $r$ pairings (so if $m > 2r$, then $p=0$). To verify that it is indeed correct, we first calculate that there are $\binom{N}{2}^r$ ways to have $r$ interactions between $N$ chromosomes (where it's important to realize that a single chromosome can interact multiple times). Now we count the fraction of those interactions in which exactly $m$ chromosomes are involved. To do so, we first pick $m$ chromosomes, which gives the factor $\binom{N}{m}$. Then, assuming that $A_{m,r}$ is equal to the number of ways we can let $m$ chromosomes interact $r$ times with each other, such that each of those $m$ chromosomes is involved in at least one interaction, we have that $$p = \frac{\binom{N}{m} A_{m,r}}{\binom{N}{2}^r}.$$ Therefore, we are finished if we can show that $$A_{m,r} = \sum_{k=0}^{m-2} (-1)^k \binom{m}{k} \binom{m-k}{2}^r.$$ But this is as you already assumed just the inclusion exclusion principle (I describe this without much formalism in the hope that it's better understandable): First you count all possible ways to let the $m$ chromosomes interact $r$ times, which gives $\binom{m}{2}^r$. Now you subtract all those ways where at least one chromosome is not involved (choose the chromosome which does not interact, which gives $\binom{m}{1}$, then let the remaining $m-1$ ones interact in all possible ways, giving $\binom{m-1}{2}^r$): $$\binom{m}{2}^{r} - \binom{m}{1} \binom{m-1}{2}^r$$ Now you have to add all those ways in which at least two chromosomes are not involved ($\binom{m}{2} \binom{m-2}{2}^r$ possibilities, again first pick the two which are not involved, then distribute the $r$ interactions among the remaining $m-2$) and so forth, giving the stated identity for $A_{m,r}$ and finishing the proof.