1
$\begingroup$

I tried two methods here. First, the usual one of checking different arrangements with a 3,1,1 distribution and the other with a 2,2,1 distribution and calculating their respective combinations. Works out to a total of 108. Again a long method. So wanted a shorter one.

Then i tried the "Stars & Bars" approach. I first gave each row a ball so am left with 2 balls and 6 spaces to fill. But somehow I am unable to arrive at the right answer. Could someone help point out the flaw in reasoning? Thanks.

$\endgroup$
  • $\begingroup$ Your reasoning is sound, but don't forget that there are multiple ways of putting a ball in each row. Also, be careful to not count solutions multiple times. $\endgroup$ – zuggg Jul 11 '13 at 12:23
  • $\begingroup$ Could you elaborate with giving a headstart? I seem to be stuck. $\endgroup$ – Sharon Jul 11 '13 at 12:24
  • $\begingroup$ Do you mean that there can be no more than one ball per cell? And there are no restrictions on columns? $\endgroup$ – Maesumi Jul 11 '13 at 13:07
  • $\begingroup$ Each "row" should necessarily have a ball. Not each cell. There are 5 balls and 9 cells. @Maesumi $\endgroup$ – Sharon Jul 11 '13 at 13:10
2
$\begingroup$

It may be easier to count the number of ways to place the balls into only two rows, then subtract this from the total number of ways to place 5 balls on the grid in any arrangement. In order to use only two rows, one row must have 3 balls, and the other 2 -- there are $3! = 6$ ways to choose which row has 3 balls and which has 2. On the row with two balls, there are three distinct configurations (choose which space to leave empty). Therefore, the number of ways to place 5 balls in 2 rows is: $$ 3! \cdot 3 = 18. $$ Finally, count the number of possible arrangements of the 5 balls on the $3 \times 3$ grid: $$ \binom{9}{5} = 126. $$ Thus, the number of ways the 5 balls can be arranged with at least 1 ball on each row is: $$ 126 - 18 = 108. $$

$\endgroup$
  • $\begingroup$ Thanks for the method. @Shaun Ault $\endgroup$ – Sharon Jul 11 '13 at 12:52
  • $\begingroup$ @Shaun What if the question was " There are 5 identical balls to be placed in the square boxes (3x3 grid). A box can contain one ball at a time. The five balls have to be placed in the squares in such a way that any row or column must contain at least one ball. There cannot be any row or column left vacant. Find the number of ways this can be done. " How to find the total cases in which either a row or column is vacant? $\endgroup$ – mac07 Aug 28 '16 at 3:50
0
$\begingroup$

You may double count the rows which have more than 1 ball. E.g., For 5 balls located at (1, 1), (1, 2), (2, 1), (2, 2), (3, 3) (where (x, y) means a ball located at x-th row and y-th column), according to the "Stars & Bars" approach, you may count it four times.

$\endgroup$
  • $\begingroup$ But it's a 3x3 grid?! @Yuandong $\endgroup$ – Sharon Jul 11 '13 at 12:29
  • $\begingroup$ Yeah, the coordinates range from 1-3. So what do you mean? $\endgroup$ – Yuandong Jul 11 '13 at 12:34
0
$\begingroup$

First assign $1$ ball to each row and each of these three balls can take $3$ positions in each respective row. So no of ways of assigning $1$ ball in each row is $3\cdot 3\cdot 3.$ Now we are left with $2$ balls (as $3$ have been assigned) and $6$ places (as $3$ places already filled) so the number of ways in which $2$ balls arranged in $6$ places is $6P2$

Answer= $3^3 \cdot 6P2$

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