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 Tey
    Oct 5, 2019 at 14:49
  • $\begingroup$ typo alert? i think you meant to say 8 different colors (2nd paragraph of Background section). $\endgroup$
    – antkam
    Oct 5, 2019 at 16:26
  • $\begingroup$ Whoops, thanks for catching that! $\endgroup$
    – Sten
    Oct 5, 2019 at 16:43

1 Answer 1

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, 2019 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .