# In how many ways can 5 identical balls be placed in a (3x3) grid such that each row contains atleast one ball?

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.

• 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. – zuggg Jul 11 '13 at 12:23
• Could you elaborate with giving a headstart? I seem to be stuck. – Sharon Jul 11 '13 at 12:24
• Do you mean that there can be no more than one ball per cell? And there are no restrictions on columns? – Maesumi Jul 11 '13 at 13:07
• Each "row" should necessarily have a ball. Not each cell. There are 5 balls and 9 cells. @Maesumi – Sharon Jul 11 '13 at 13:10

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

• Thanks for the method. @Shaun Ault – Sharon Jul 11 '13 at 12:52
• @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? – mac07 Aug 28 '16 at 3:50

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.

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

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$