0
$\begingroup$

Suppose we have 4 golfballs and 10 boxes. We want to find the number of ways to distribute those balls into the boxes assuming that the balls are indistinguishable and each box can hold any number of balls.

my thought

We can call $x_i$ the number of balls in box $i$. And we want

$$ x_1 + x_2 + .... + x_{10} = 4 $$

and the number of solutions of this equation is ${10+4-1 \choose 10 -1} = {13 \choose 9 } $.

However, my answer key claims the solution is ${13 \choose 4}$. What am I doing wrong? I would appreciate any criticism!

$\endgroup$
2
  • 1
    $\begingroup$ ${13 \choose 4} = {13 \choose 9}$ because in general, ${n \choose k} = {n \choose n-k}$ (in this case $n=13, k=4$). $\endgroup$
    – Toby Mak
    Commented Feb 24, 2020 at 5:04
  • $\begingroup$ but did they arrive at 13 choose 4. I was wondering about that $\endgroup$
    – James
    Commented Feb 24, 2020 at 5:13

1 Answer 1

1
$\begingroup$

The usual method is to choose the bars out of the stars and bars, fixing the stars in place. If there are $n$ stars and $k-1$ bars, this would be ${n+k-1 \choose k-1}$.

However, if we choose the positions of the stars first (say star $1$ is first, then a bar is second, and star $2$ is third), the bars will be fixed in place. Choosing either the stars or the bars will make no different, since the rest of the positions must be of the other type.

Therefore the number of ways to choose the stars is ${n+k-1} \choose n$, or ${4+9-1} \choose 4$ in your example.

Sidenote: Brilliant and Wikipedia have good articles explaining this.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .