2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.