# In how many ways can $5$ identical balls be placed in the cells of a $3 \times 3$ grid such that each row contains at least one ball?

In how many ways can $5$ identical balls be placed in the cells of a $3 \times 3$ grid such that each row contains at least 1 ball?

I proceeded like this- In the first row choosing one cell out of $3$ is $3\choose1$, similarly $3\choose1$ for choosing one cell from 2nd row and third row. Now from remaining $6$ cells we can place remaining $2$ balls as $6\choose2$.

Thus the solution should be $\binom31\cdot\binom31\cdot\binom31\cdot\binom62$.

But it isn't the right answer. Could anybody help me out? The right answer is 108.

For a given configuration $c$ let $R_c$ denote the multiset counting the number of balls in each row. We have two cases:

First case: $R_c = \{3, 1, 1\}$

For the row of 3 balls, we have only one configuration, i.e. all cells have a ball. For each row of 1 ball, we can put the ball in one of 3 positions. Also, we have 3 options of which of the three rows holds the 3 balls. Hence the number of configurations that have $R_c = \{3, 1, 1\}$ is $3 \cdot 3 \cdot 3 = 27$.

Second case: $R_c = \{2, 2, 1\}$

For each row of 2 balls we have 3 configurations (the vacant spot can be one of three cells). For the row of 1 ball we also have 3 configurations (the occupied spot can be one of three cells). Finally, we have 3 permutations of the rows. Hence the number of configurations here is $3 \cdot 3 \cdot 3 \cdot 3 = 81$.

Summing them we get $27 + 81 = 108$.

The problem with your approach is that you're not looking at independent variations that make up your configuration. Once you select 1 ball for each row (which gives you $3 \choose 1$ options), you cannot simply add new balls to that row, because that changes the number of variations for that row. For example, if you add 2 balls to a row with 1 ball, then the number of configurations for that row will be 1, not 3.

Using the fact that at most 1 row can be empty, subtract from the total ${9\choose 5}$ = 126 ways,

ways in which one row is full, one empty, and one with just 1 vacant slot.

There are 3! ways to permute the rows, and 3 ways to position the 1 vacant slot

Thus $126 - 3!\cdot 3 = 108$