3
$\begingroup$

I have 10 balls(no distinction between them), i want to restribute all of them to 4 baskets(a basket can have them all and the others can be empty),so i care about counting how many ways i can put those balls into 4 baskets.

(basket1,basket2,basket3,basket4) some correct combinations are (0,10,0,0),(1,9,0,0),(1,1,1,7) and so on, is there some formula that can help me with that?

After some trial and error i thought about (k+n-1)!/n!(k-1)! which gives me (4+10-1)!/10!(4-1)! = 286 ways (is my thought correct?, if so why exactly?)

2nd question:what if i want basket number 4 to have ALWAYS at least 1 ball, i thought that possible ways to put balls from 10 balls to 1 basket is 10ways so i used above formula again to (now i have 3 baskets and at best case 9 people) (3+9-1)!/9!(3-1)! = 55ways meaning 55*10=550 ways.Is my thinking process correct?

$\endgroup$
  • 2
    $\begingroup$ It is incorrect to multiply with $10$ in your second answer. The balls are not distinguishable. You just put a ball in the basket4 (only one possibility) and after that you divide $9$ balls over all baskets. Further see stars and bars for this. $\endgroup$ – drhab Oct 18 '18 at 18:14
1
$\begingroup$

You are correct for the first problem but not the second. Represent each ball by $\star$ and the separations between baskets by $\vert$. Then a typical arrangement would be, for example, $$\star\star\star\star\vert\star\star\star\star\star\vert\ \vert\star$$ In this case, the baskets hold $4, 5, 0,$ and $1$ ball, respectively. The number of ways to do this is $${\textrm{# symbols} \choose \textrm{#stars}} = {10 + 4 - 1 \choose 10}$$ As for the second problem, it is a restricted version of the first, so you should be skeptical that you ended up with a greater number of possibilities. The simple way to do the second problem is to start with one ball in the fourth basket, then ignore it. Now you have $9$ balls to distribute in $4$ baskets, so the calculation will be as above, but with $9$ instead of $10$.

$\endgroup$
1
$\begingroup$

This is the same as solving equation $a+b+c+d = 10$ in nonegative integers which as writing 10 stars and 3 bars in a row. So the answer is $${13\choose 10}$$


Explanation: Say $a=3, b=2, c= 4$ and $d=1$. It is the same as writing $$***|**|****|*$$ and vice versa. What does $$*****||***|**$$ mean? It means that $a=5$, $b=0$, $c=3$ and $d=2$.

So for each $(a,b,c,d)$ we have a uniqe patern of $10$ stars and $3$ bars and vice versa. So the number of solution of that equation is the same as number of that paterns.

$\endgroup$
1
$\begingroup$

You are correct for the first part. This is an application of a technique called "stars and bars". Imagine we biject each configuration of balls in baskets to strings whose characters are $*$ and $\vert$ in the following way: the amount of stars between bars $i$ and $i-1$ will be the number of balls in the $i$th basket. So for example a string $**\vert***\vert\vert*****$ will correspond to $2$ balls in the first basket, $3$ balls in the second basket, $0$ balls in the third basket, and $5$ balls in the fourth basket.

So we have a $13$ digit string where $13 = 10 + 4 - 1$ is the number of balls plus the number of separators (i.e. baskets minus $1$) and we choose $10$ of these characters to be $*$. This gives $\binom{n+k-1}{n}$ which is what you came up with.

For your second question, you're almost correct. There is no need to remove one basket, though you should remove one ball. You also shouldn't distinguish between your balls. So the answer would just be $\binom{9+4-1}{9}$ following the logic of the first part.

$\endgroup$
1
$\begingroup$

I agree on the stated solutions to the first part. Another way to consider for solving the second part is to remove all ways in which the fourth bucket is empty. Using stars and bars, this is like taking away one of the partitions, allowing combinations such as $$***|*****|**|$$In this case, the number of ways is $\binom{13}{3}$, the ways of putting balls into all four buckets, minus $\binom{12}{2}$, the ways of putting balls into only three buckets.

(Note the symmetry between $\binom{x}{y}$ and $\binom{x}{x-y}$; I choose on "bars" vs. "stars." The answer is the same either 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.