1
$\begingroup$

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?

3x3_grid

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

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