# Showing that two combinatorial expressions are equal

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

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

## 1 Answer

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.

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