1
$\begingroup$

It's Friday, and I'm tired, so there possibly a trivial solution that I am overlooking ...

The problem is the following: I have ($n=2$) two kinds of things, say Apples and Bananas, and I choose $k$ of these, not minding the order in which I take them.

What is the possible number of combinations, given that I only have $\alpha$ Apples and $\beta$ Bananas? (\alpha+\beta>k, but typically $\alpha<=k$ or $\beta<=k$ or both). And how many solutions are there that include exactly $\gamma<=\alpha$ Apples?

(I think that without the limits the solution would be an application of the multiset-number/stars-and-bars, with n and k. However, these solutions assume a unlimited supply of fruit, and I cannot see a way to adapt that these results to my limits.)

  • 1
    They're Fuji and Granny Smith apples.2011-05-06

1 Answers 1

3

Choosing $\gamma$ apples you must have $k-\gamma$ bananas (if $\gamma \ge k-\beta$). That is the only way, unless you are going to distinguish the apples and distinguish the bananas, in which case there are ${\alpha \choose \gamma}{\beta \choose k-\gamma}$ ways.

Add these up over $\gamma$ and you get your answer: either

$\sum_{\gamma=\max(0,k-\beta)}^{\min(k,\alpha)} 1 $

if you are not going to distinguish the apples and distinguish the bananas, or

$\sum_{\gamma=\max(0,k-\beta)}^{\min(k,\alpha)} {\alpha \choose \gamma}{\beta \choose k-\gamma} $

if you are.

The first of these is equal to $\alpha+\beta+1-k$, provided that $ 0 \le k - \beta < \alpha \le k$.

  • 0
    In fact, I realized I have to distinguish the apples and bananas only after writing the question (and reading your answer).2011-05-09