2
$\begingroup$

Good Day! How are you doing?

I recently learnt that the formula for the number of non-negative solutions to the equation ${x_1 + x_2 + ... + x_r = n}$ is ${n+r-1 \choose r-1}$. It can also be easily proven using the circles and bars (or whatever you wanna call it). But my reasoning was as follows:

To find the number of non-negative integer solutions to the equation ${x_1 + x_2 + ... + x_r = n}$, suppose that there are $n$ balls and $r$ boxes to put it. Then the number of ways to put the $n$ balls into $r$ boxes is ${r^n}$ (There are $r$ ways to put the balls into the boxes). But this is clearly different.

I know I am over-counting but I don't know how exactly. I would be grateful to you if you helped me. I know I am missing out on something and not realizing it. This question may sound stupid or trivial to you, but I am just not able to realize where I am over-counting.

Thanks!

$\endgroup$
6
  • 6
    $\begingroup$ You are assuming the balls are all different (distinguishable). $\endgroup$
    – Michal Adamaszek
    May 15, 2019 at 11:36
  • $\begingroup$ The correct expression is $\binom{n+r-1}{r-1}$ or $\binom{n+r-1}n$. $\endgroup$
    – user
    May 15, 2019 at 11:43
  • $\begingroup$ @user It depends on whether $n$ represents the number of balls and $r$ the number of bins, or if it is the other way around with $n$ representing the number of bins and $r$ the number of balls. $\binom{n+r-1}{r}$ is a perfectly correct result if you use the corresponding choice of what $n,r$ stand for. See this question. $\endgroup$
    – JMoravitz
    May 15, 2019 at 11:44
  • 1
    $\begingroup$ Try a simple example like $n=2,r=2$ and see why the number of non-negative solutions to the equation is $3$ rather than $4$. Then consider your balls and boxes and @MichalAdamaszek's comment to see why the balls are indistinguishable here $\endgroup$
    – Henry
    May 15, 2019 at 11:50
  • $\begingroup$ @JMoravitz $n$ and $r$ are not arbitrary. They are defined in the question so that $n$ counts "balls" and $r$ counts "bins". $\endgroup$
    – user
    May 15, 2019 at 16:17

1 Answer 1

Reset to default
4
$\begingroup$

The following questions are all different and with different answers:

  • How many ways can you distribute $n$ distinct balls among $r$ distinct boxes? $r^n$

  • How many ways can you distribute $n$ indistinct balls among $r$ distinct boxes? $\binom{r+n-1}{n}$

  • How many ways can you distribute $n$ distinct balls among $r$ indistinct boxes? $\sum\limits_{k=0}^r \left\{\begin{matrix}n\\k\end{matrix}\right\}$

  • How many ways can you distribute $n$ indistinct balls among $r$ indistinct boxes? $p_r(n+r)$

You were confusing the original problem with the first of these where your balls were distinct when it should have been in the second case where the balls were in fact considered indistinct.

Read more about these and the notations used and other similar problem variants where you require at least or at most one ball in each bin at https://en.wikipedia.org/wiki/Twelvefold_way.

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