4
$\begingroup$

I need to find the number of ways to distribute a varying number of balls into 3 distinct boxes such that the sum of all balls is $\le 99$.

Since the balls are identical and the boxes are distinct, I have chosen to use $H^n_r$ i.e. ${r+n-1}\choose{r}$ to solve the problem, where $n$ = number of boxes and $r$ = number of balls.

I have split the problem into different cases, such as when sum of balls is 99, sum of balls is 98.. all the way to if the sum of balls is 0.

I have obtained the following sequence

${101}\choose{99}$ + ${100}\choose{98}$ + ${99}\choose{97}$ +...+ ${3}\choose{1}$ + ${2}\choose{0}$

Using the symmetry rule I have simplified this into

${101}\choose{2}$ + ${100}\choose{2}$ + ${99}\choose{2}$ +...+ ${3}\choose{2}$ + ${2}\choose{2}$ = $\sum_{r=2}^{101}{{r}\choose{2}}$

However I feel that my method is too long, is there some kind of way to simplify the answer even more so that I can get an integer solution?

$\endgroup$

1 Answer 1

8
$\begingroup$

The following is a one-step answer.

You can take a dummy variable $d\ge 0$ such that you are actually filling the $n=3$ boxes with $r=99-d$ balls, so that you have $$a_1+a_2+a_3+d=99$$ where $a_i$ is the number of balls in the $i^{th}$ box,
and we have the restriction, $a_i,d\ge 0 \forall i\in \{1,2,3\}$
which has $\binom{99+4-1}{4-1}=\binom{102}{3}$ many solutions.

However, the sum you have is not too hard to calculate, you just have to use Pascal's identity: $$\binom{n}{r}=\binom{n-1}{r}+\binom{n-1}{r-1}$$ with $r=3$ again and again, starting with writing the last term in your obtained sum $\binom22=1=\binom33$ and then reducing in each step, the underlined part, to get the last term in the next step $$\binom{101}2+\binom{100}2+\cdots +\binom42+\underline{\binom32+\binom33} \\ =\binom{101}2+\binom{100}2+\cdots +\binom52+\underline{\binom42+\binom43} \\ = \binom{101}2+\binom{100}2+\cdots +\binom62+\underline{\binom52+\binom53}\\ \vdots \\ = \underline{\binom{101}2+\binom{101}3}=\binom{102}3$$

$\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.