0
$\begingroup$

Suppose I have already placed five balls in a straight line. In how many ways can I place three identical balls between them, if more than one ball can be placed between two balls?

$\endgroup$
  • 2
    $\begingroup$ Try and count how many ways are possible when you place the 3 balls together, then when you place 2 balls together and one alone, and finally when no balls are together. $\endgroup$ – krirkrirk Jul 5 '17 at 10:19
  • 1
    $\begingroup$ I take it there are 4 spaces, not 6? And they're not in a circle (in which case there would be 5 spaces! $\endgroup$ – samerivertwice Jul 5 '17 at 10:21
  • 1
    $\begingroup$ Assuming the balls are indistinguishable you have $4$ gaps hence you want to count $4$-tuples of non-negative numbers that add to $3$. You can do that directly or you could invoke Stars and Bars $\endgroup$ – lulu Jul 5 '17 at 10:21
  • 1
    $\begingroup$ Looks like $4+12+4=20$ $\endgroup$ – samerivertwice Jul 5 '17 at 10:23
  • 1
    $\begingroup$ @RobertFrost I suggest you turn your comments into an answer. $\endgroup$ – N. F. Taussig Jul 5 '17 at 11:05
0
$\begingroup$

This problem is a stars-and-bars problem. We have to divide three indistinguishable balls among four slots (the positions in between the five balls). It thus comes down to selecting the position of the three bars, which divide the four slots. As such, the number of possible arrangements equals:

$${3 + 4 - 1 \choose 4 - 1} = {6 \choose 3} = \frac{6!}{3!3!} = 20$$

$\endgroup$
  • $\begingroup$ That's it ! Thank you all very much ! $\endgroup$ – Andrei Muntean Jul 5 '17 at 17:59
2
$\begingroup$

Assume that 4 intermediate places generated by 5 balls are distinguishable.

Let the 3 balls to be placed are distinguishable.

${}^4P_3 + {}^3C_2 {}^4P_2 + {}^4P_1$ ways

Answer is obtained as follows: You can take 1 ball each and permute them into 4 slots available. You can divide the balls into $2 + 1$ combinations and this can be done in ${}^3C_2$ ways and are distinguishable. Then, for each of the combinations, you can permute them with ${}^4P_2$ possible ways. Finally, you can take 3 balls together, which can be done in ${}^3C_3$ ways. You can distribute these combinations in ${}^4P_1$ ways.

Let the 3 balls to be placed are undistinguishable.

${}^4C_3 + {}^4P_2 + {}^4P_1$ ways

Answer is obtained as follows: You can take 1 ball each, but they are undistinguishable then apply combinations to put them into 4 slots available. You can divide the balls into $2 + 1$ combinations and this can be done in only 1 way and now the groups so generated are distinguishable. You can permute them with ${}^4P_2$ possible ways. Finally, you can take 3 balls together, which can be done in only 1 way. You can distribute these combinations in ${}^4P_1$ ways.

$\endgroup$
  • $\begingroup$ Why are you using permutations for identical balls? $\endgroup$ – N. F. Taussig Jul 5 '17 at 10:59
  • $\begingroup$ Balls are identical. But slots are not. E.g. aa.a and a.aa are different. $\endgroup$ – Eval Jul 5 '17 at 11:01
  • $\begingroup$ Your answer is incorrect. Here is a program for solving the problem. 1. All three balls are together: In how many can all three balls be placed in one of the four available positions? 2. Two balls are together and one is separate: In how many ways can you choose a position for two of the balls and a separate position for the third ball? 3. No two of the balls are together: In how many ways can you choose three separate positions for the three balls? $\endgroup$ – N. F. Taussig Jul 5 '17 at 11:04
  • $\begingroup$ Let . represent empty space. Then with 3 ball together, you have (aaa)...,.(aaa)..,..(aaa).,...(aaa) count them. There are 4 possible positions. a.aa,aa.a,aaa.,.aaa count them. There are 4 possible location. For 2 distingushable ball in 4 distinguishable location it has to be 4P2 ways. $\endgroup$ – Eval Jul 5 '17 at 11:08
  • $\begingroup$ Agreed. The error you made was in counting the number of ways three indistinguishable balls can be placed in three separate positions. $\endgroup$ – N. F. Taussig Jul 5 '17 at 11:13
2
$\begingroup$

There are 4 places between the 5 balls.

The 3 balls to be placed can be grouped in the following ways:

  1. All 3 balls together in one space, with none in the remaining 3 spaces.
  2. Two of the balls in one space, the remaining ball in another, and the final two spaces empty
  3. Each ball in a different space, with one space empty

Case 1: This can be done in 4C1 ways: 4

Case 2: This can be done in 4P2 ways: 12

Case 3: This can be done in 4C3 ways: 4

Therefore the answer is 4 + 12 + 4 =20

$\endgroup$
2
$\begingroup$

There are $4$ spaces.

Start by seeing how many ways you can partition $3$ into up to $4$ parts with zeroes permitted. You can partition it into $3,0,0,0$ or $2,1,0,0$ or $1,1,1,0$

Now count the number of ways you can order those sets among the four spaces.

The first; well there are $4$ positions the $3$ can take and then the zeroes are determined.

the second; there are $4$ positions for the $2$ leaving $3$ positions for the $1$ and then the zeroes are determined.

And the third; there are $4$ positions the zero can take and then the ones are determined.

This gives you $4+12+4=20$

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