Compute $$\sum\limits_{k+l=0}^{97}\binom{100}{k}\binom{100-k}{l}\binom{100-k-l}{97-k-l}$$

My Attempts

We already khow that $\quad k+l=0 \quad$ and $\quad l=-k \quad $ so we can say that this expression actually is $$\sum_{k+l}^{97}\dbinom{100}{k}\dbinom{100+l}{l}\dbinom{100}{97}$$ luckily we can factor out $\dbinom{100}{97}$ from the sum and $$\dbinom{100}{97}\left(\sum_{k+l=0}^{97}\dbinom{100}{k}\dbinom{100+l}{l}\right)$$ my problem is about calculating this sum, do we say that $k+l=0$ always?

Or do we say that oh Ok! $k+l=0$ and now its $k+l=1$ and now $k+l=2 \cdots$

Which one is true?

And if $k+l=0$ always then how come $k,l \in \mathbb{Z}^+$ and if they are not how can I use negative bases in binom?

  • $\begingroup$ $l$ is not equal to $-k$. $k+l$ is the value that increases $\endgroup$ – MCCCS Sep 18 '17 at 15:19
  • $\begingroup$ I see thanks:) Now how can I simplify this expression and how can I calculate it most importantly? $\endgroup$ – Deniz Tuna Yalçın Sep 18 '17 at 15:22
  • $\begingroup$ @MCCCS I actually was wondering about that. So it's all pairs of values of $k,l \geq 0$ that add up to something less than $98$? $\endgroup$ – John Sep 18 '17 at 15:22
  • $\begingroup$ @John Yep. So one can assume $k=0$ and solve the problem easier by just incrementing $l$. $\endgroup$ – MCCCS Sep 18 '17 at 15:27
  • $\begingroup$ @MCCCS And the result of this wouldn't change if we keep one variable fixed like $k=0$ (fixed)? $\endgroup$ – Deniz Tuna Yalçın Sep 18 '17 at 15:29

You are counting the ways of how to paint an arbitrary number $k$ of $100$ balls red, an arbitrary number $l$ of the remaining $100-k$ balls blue, and $97-k-l$ of the remaining $100-k-l$ balls green.

In the end you have simply left $3$ balls uncoloured and assigned arbitrary colours from the three available colours to all other balls. Therefore $$\sum_{k+l=0}^{97}{100\choose k}{100-k\choose l}{100-k-l\choose 97-k-l}={100\choose 3}\cdot 3^{97}. $$

| cite | improve this answer | |
  • $\begingroup$ This is one incredible solution, thank you:) $\endgroup$ – Deniz Tuna Yalçın Sep 18 '17 at 15:32


Assume $k=0$ and increment $l$







| cite | improve this answer | |
  • $\begingroup$ Hello @MCCCS It makes a lot of sense but I failed to find something like $3^x.\dbinom{100}{\text{something}}$ what did you get doing these calculations? $\endgroup$ – Deniz Tuna Yalçın Sep 19 '17 at 5:01
  • $\begingroup$ @DenizTunaYalçın Yes, you're right, I got stuck at $\frac{100!}{6}\sum_{l=0}^{97}\frac{1}{(97-l)!l!}$ $\endgroup$ – MCCCS Sep 19 '17 at 15:20
  • $\begingroup$ I think before assuming $k=0$ if we say $\dbinom{100}{k+l}\dbinom{k+l}{l}\dbinom{100}{3}$ for the existing expression this explains $\dbinom{100}{3}.\cdots$ however I still can't get a power of $3$. $\endgroup$ – Deniz Tuna Yalçın Sep 19 '17 at 15: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.