2
$\begingroup$

In how many ways 8 candies can be distributed be among 3 children?

I have done by using combination method $8C4$ but the answer is given 45. someone has done in this way:

  1. 008 in 3 ways
  2. 710 in 6 ways

  3. 611 in 3 ways

  4. 620 in 6 ways

  5. 530 in 6 ways

  6. 521 in 6 ways
  7. 440 in 3ways
  8. 431 in 6 ways
  9. 422 in 3 ways

  10. 332 in 3 ways

    in total 45 ways.

    Why my formulation is not right. And how can I do this math within the formula I have writen? I mean within short time done.

$\endgroup$
3
  • 1
    $\begingroup$ The Stars and Bars method is by far the most efficient way. The careful cases analysis you listed is lengthy, and with so many calculations it is possible for errors to creep in. For $3$ kids A,B,C one could say maybe A gets $0$ (easily $9$ ways, B gets $0$ to $8$). Maybe A gets $1$ ($8$ ways). And so on to A gets $8$ ($1$ way). Total is $9+8+\cdots+1=(9)(10)/2=45$. $\endgroup$ – André Nicolas Sep 23 '13 at 20:29
  • $\begingroup$ I think the question involving four candles is much more interesting (sorry!) $\endgroup$ – David Ward Sep 24 '13 at 8:20
  • $\begingroup$ what happen if number of kids are 5 ? $\endgroup$ – mathphy Sep 25 '13 at 14:30
6
$\begingroup$

Original Answer

Seeing as you asked me to look at this problem for you I'll give my own answer. I get that your main concern here is understanding and not just being given the correct solution. But, correctness has a context. Your formulation, although lengthy has none the less given the correct answer.

If you don't understand how to prove the stars and bars formula, instead I'll show you a method using the basic idea of the stars and bars diagram to hopefully understand what is going on. From this you may go on to understand the proof.

The two bars stand between the three children. Start with the two children on the left with no sweets and the child on the right with all of them. Leave the left most bar at the left and move the right hand bar, past one star at a time, to the right. (This first one is equivalent to (0, 0, 8))

$$\ |\ |\ \bigstar\bigstar\bigstar\bigstar\bigstar\bigstar\bigstar\bigstar$$

The following is what it looks like after two steps to the right (which is equivalent to (0, 2, 6))

$$\ |\ \bigstar\bigstar\ |\ \bigstar\bigstar\bigstar\bigstar\bigstar\bigstar$$

You can do this 8 times. So the first step has 9 combinations.

Then put the two bars after the first star and again leave the left hand bar where it is and move the right hand bar, one at a time to the right. (This one is equivalent to (1, 0, 7))

$$\ \bigstar |\ |\ \bigstar\bigstar\bigstar\bigstar\bigstar\bigstar\bigstar$$

You can do this 7 times. So the second step has 8 combinations.

You should be seeing a pattern by now.

Each step decreases by one. The last step has the two bars on the far right with the right hand bar having nowhere else to go, finishing with 1 combination. Thus the pattern gives you a triangular number.

Total = 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45

Addendum 1: Stars And Bars Proof

Stars and Bars Theorem $n\leq k$: We have $n$ containers and $k$ identical items to distribute. If you start by insisting that each container has at least 1 item in it, you may as well start by putting 1 item into each container. You have no choice with this. Hopefully you can see that, counting wise, this is the same as starting with $k-n$ items and allowing empty containers.

So, lets start with $k$ items, $n$ containers and insist at least one in each container. In the following argument this allows having gaps only between stars. If we tried to start with having empty containers, you have a problem with bars accumulating at the edges and the argument doesn't work.

Consider the following diagram with $k=11$ and $n=4$. The 3 bars represent the boundaries between separate containers, where $3=4-1$. We can't put bars at the left and right hand edges, otherwise that would mean we had a container at the right or left or both ends with no items in so the outside edges are automatically boundaries of the first and last containers.

\begin{align*} |\ \bigstar\bigstar\bigstar\bigstar\bigstar\bigstar\ |\ \bigstar\bigstar\ |\ \bigstar\bigstar\bigstar &= (0, 6, 2, 3) \text{ this is not allowed } \\ \bigstar\ |\ \bigstar\bigstar\bigstar\bigstar\bigstar\ |\ \bigstar\bigstar\ |\ \bigstar\bigstar\bigstar &= (1, 5, 2, 3) \text{ this is allowed } \end{align*}

Think of this as allocating the gaps between stars to the bars and note also that you can't have more than one bar in a single gap, otherwise we wouldn't be able to apply the standard combinations formula. So, we have in general $k$ stars, $k-1$ gaps between them to choose from and $n-1$ bars to distribute in them, which gives ${{k-1}\choose{n-1}}$ ways.

As above, insisting on at least 1 in each container, is the same as having $k-n$ items and allowing 0 in any container. So, if we distribute $k+n$ items into $n$ containers with at least 1 in each container, this is the same, counting wise, as distributing $k$ items into $n$ containers allowing 0 in any container.

Thus we have $${{k+n-1}\choose{n-1}} = \frac{(k+n-1)!}{((k+n-1)-(n-1))!(n-1)!} = \frac{(k+n-1)!}{k!(n-1)!} = {{k+n-1}\choose{k}}.$$

$\endgroup$
8
  • $\begingroup$ what happen if number of kids are 5 ? $\endgroup$ – mathphy Sep 25 '13 at 14:29
  • $\begingroup$ Calculating for 5 by hand is a bit messy. At some point you have to try and understand the simpler cases and then trust the general stars and bars formula. There's a very good proof on a page on wikipedia. They prove the case where no bin (child) can be empty (no sweets). Then they use this to prove the case where any bin can be empty. It's nicely explained. $\endgroup$ – Geoff Pointer Sep 25 '13 at 14:47
  • $\begingroup$ I have understood that you used stars for 8 candies but how did you use 3 children? $\endgroup$ – mathphy Sep 25 '13 at 15:39
  • 1
    $\begingroup$ The bars are between the children, that's why there are two bars for three children. The bars separate the children. As you move the bars around there are always three groups of stars, one group for each child. My middle diagram above has 0 stars on the left for the first child, 2 stars in the middle for the second child and 6 stars on the right for the third. You only need (n-1) bars to separate n children. $\endgroup$ – Geoff Pointer Sep 25 '13 at 15:49
  • $\begingroup$ I understand now. then more children will come and the calculation will be more complicated, isn't it? IS there any way to get the answer quickly for more bars? $\endgroup$ – mathphy Sep 25 '13 at 16:01
1
$\begingroup$

If you're planning on using the stars and bars method, it is given by $$\binom{8+3-1}{8}=45.$$

We have eight candies (or stars) and two bars that separate the candies. E.g. $$\star\star|\star\star\star\star\star|\star$$ corresponds to the children receiving $2$, $5$, and $1$ candies, respectively. And there are $\binom{8+3-1}{8}$ inequivalent ways to sequence the stars and bars.

$\endgroup$
2
  • $\begingroup$ my question was also, why my formula was wrong? and why d we using stars and bars method? $\endgroup$ – mathphy Sep 24 '13 at 7:10
  • $\begingroup$ I'm not sure how to explain why it's wrong: almost every formula we could write down will be wrong. $\binom{8}{4}$ counts the number of ways of choosing a subset of size $4$ from a set of size $8$, and doesn't seem to relate to the problem at all (unless it were an attempt at the stars and bars method). I highlight above how the stars and bars method works in this particular instance. $\endgroup$ – Rebecca J. Stones Sep 24 '13 at 10:15
-4
$\begingroup$

There is a formula for working this out called the related to the binomial coefficient it is: n!/(n-k)!k!, where n is the number of sweets and k is the number of children

Using the formula there are 112 possible combinations of sweets and children

$\endgroup$
3
  • $\begingroup$ mathworld.wolfram.com/BinomialCoefficient.html $\endgroup$ – user96203 Sep 23 '13 at 20:05
  • $\begingroup$ Your answer is incorrect. If there were 8 different sweets and the 3 children were getting exactly 1 each and you keep the rest, then ${{8}\choose{3}}$ is the correct answer. But, this problem, in its general form, is about having $k$ items, exactly the same, and distributing them into $n$ containers. It's not a simple combination problem. $\endgroup$ – Geoff Pointer Sep 25 '13 at 23:02
  • $\begingroup$ I obviously rushed that comment, because it's only the answer to subsets of 3 out of eight different sweets. The children are different also and so $P^8_3$ would be correct. See how easily a rushed answer can go wrong? I'm surprised no one jumped on my ineptness. Doh!? $\endgroup$ – Geoff Pointer Nov 2 '13 at 1:16

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.