9
$\begingroup$

Is there an algebraic way of showing that $$\sum_{m=\lceil p / b\rceil}^{c} \left(-1\right)^m \frac{\binom{b\cdot m}{p}}{\binom{b\cdot c}{p}} \sum_{k=m}^{c}k\cdot(-1)^{k} \binom{c}{k} \binom{k}{m} = c\cdot\left[1 - \frac{\binom{b\cdot[c - 1]}{p}}{\binom{b\cdot c}{p}}\right], $$

for all positive integers $b$, $c$, $p$?

Background:

A friend sent me a puzzle, which I've solved in two different ways, and I'd like to convince myself that they're algebraically the same.

Specifically, I was asked to consider the following problem: Suppose we have 80 balls in a bowl of 8 different colours, with 10 of each colour. If we draw 15 of them without replacement, how many colours would we expect to see?

Method 1:

We can find the expected number of colours as the weighted average of the possible number of colours, with the weights being the probabilities: $\bar{k} = \sum_{k} k \cdot P_k$. To do this we need to calculate the probabilities of seeing exactly $k$ colours for all possible values of $k$.

The probability of using just one colour is 0, as $15 > 10$.

The probability of using exactly two colours is $\binom{8}{2} \cdot \frac{\binom{20}{15}}{\binom{80}{15}}$.

The probability of using exactly at most three colours is $\binom{8}{3} \cdot \frac{\binom{30}{15}}{\binom{80}{15}}$.This probability however includes some cases where we've picked only two colours. To get the probability of picking exactly three colours, we need to subtract these cases, giving: $\binom{8}{3} \cdot \left[\frac{\binom{30}{15}}{\binom{80}{15}} - \binom{3}{2}\frac{\binom{20}{15}}{\binom{80}{15}}\right]$. Using the inclusion-exclusion principle, the general probability of getting exactly $k$ colours is

$$ P_k = (-1)^{k} \frac{\binom{8}{k}}{\binom{80}{15}} \sum_{m=2}^{k}\left(-1\right)^m \binom{k}{m}\binom{10m}{15} $$

The expected number of colours can then be written as

$$ \begin{align} \bar{k} &= \sum_{k=2}^8k\cdot(-1)^{k} \frac{\binom{8}{k}}{\binom{80}{15}} \sum_{m=2}^{k}\left(-1\right)^m \binom{k}{m}\binom{10m}{15}\\ &= \sum_{m=2}^{8} \left(-1\right)^m \frac{\binom{10m}{15}}{\binom{80}{15}} \sum_{k=m}^8k\cdot(-1)^{k} \binom{8}{k} \binom{k}{m}. \end{align} $$

Method 2

Alternatively, I reasoned that for any given colour, the probability of having that colour in the draw is $P_{\mathrm{c}} = 1 - \frac{\binom{70}{15}}{\binom{80}{15}}$. If the colour is included, it contributes 1 to the total number of colours, and if not, it contributes 0. The expected value of the number of colours is then

$$ \bar{k} = \sum_{\mathrm{colours}} P_{\mathrm{c}} = 8 - 8 \frac{\binom{70}{15}}{\binom{80}{15}} $$

I can calculate both of these numbers, and for this particular case, they are the same.

What I'd like is to understand why they should be equal in general -- there's nothing in the derivations which limits us to 8 colours, 10 balls of each colour and 15 picks.

It's been a while since I had any combinatorics, so I'm a bit stuck

$\endgroup$
3
  • $\begingroup$ You might want to look into generating functions, which can be used to tackle problems like this generally. $\endgroup$ – YiFan Oct 5 '19 at 14:49
  • $\begingroup$ typo alert? i think you meant to say 8 different colors (2nd paragraph of Background section). $\endgroup$ – antkam Oct 5 '19 at 16:26
  • $\begingroup$ Whoops, thanks for catching that! $\endgroup$ – Sten Oct 5 '19 at 16:43
6
$\begingroup$

We seek to show that

$$\sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p} \sum_{k=m}^c (-1)^k k {c\choose k} {k\choose m} = c{bc\choose p} - c{b(c-1)\choose p}.$$

We have

$${c\choose k} {k\choose m} = \frac{c!}{(c-k)! \times m! \times (k-m)!} = {c\choose m} {c-m\choose c-k}$$

and we get for the LHS

$$\sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p} {c\choose m} \sum_{k=m}^c (-1)^k k {c-m\choose c-k} \\ = \sum_{m=\lceil p/b \rceil}^c (-1)^m {bm\choose p} {c\choose m} \sum_{k=0}^{c-m} (-1)^{k+m} (k+m) {c-m\choose c-m-k} \\ = \sum_{m=\lceil p/b \rceil}^c {bm\choose p} {c\choose m} \sum_{k=0}^{c-m} (-1)^{k} (k+m) {c-m\choose k}.$$

Now we have

$$m \sum_{k=0}^{c-m} (-1)^{k} {c-m\choose k} = m [[ c = m ]]$$

so that this becomes

$$ c {bc\choose p} + \sum_{m=\lceil p/b \rceil}^c {bm\choose p} {c\choose m} \sum_{k=0}^{c-m} (-1)^{k} k {c-m\choose k} \\ = c {bc\choose p} + \sum_{m=\lceil p/b \rceil}^c {bm\choose p} (c-m) {c\choose m} \sum_{k=1}^{c-m} (-1)^{k} {c-m-1\choose k-1} \\ = c {bc\choose p} - \sum_{m=\lceil p/b \rceil}^c {bm\choose p} (c-m) {c\choose m} \sum_{k=0}^{c-m-1} (-1)^{k} {c-m-1\choose k}.$$

Again we have

$$\sum_{k=0}^{c-m-1} (-1)^{k} {c-m-1\choose k} = [[c-1 = m]]$$

so we find

$$c {bc\choose p} - {b(c-1)\choose p} (c-(c-1)) {c\choose c-1} = c {bc\choose p} - c {b(c-1)\choose p}.$$

This is the claim.

$\endgroup$
1
  • $\begingroup$ Wow, thanks a bunch! I'd never have got there on my own. $\endgroup$ – Sten Oct 5 '19 at 17:24

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.