My question is similar to this which I think is a part of my question. I hope I'm not creating a duplicate here.

Question :
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.

I'm not able to find the total number of cases in which either a row or column is vacant.

Answer is 90 for this problem.

  • $\begingroup$ Your header directly contradicts the body of your question. I have gone by the body. Pl. correct header/body, according to your actual intentions. $\endgroup$ – true blue anil Aug 28 '16 at 6:34

Assume the bottom row is unoccupied. There are ${6 \choose 5}$ ways to place the balls in the top two rows. The same is true for the middle or top rows. By symmetry, we get the same for columns as well.

So a total of $6\cdot {6 \choose 5} = 36$ ways to have a vacant row or column.

There are ${9\choose 5} = 126$ ways to place the $5$ balls in the $3\times 3$ grid. Therefore there are

$$126 - 36 = \fbox{90}$$

ways to place the balls with no row or column vacant.

  • 1
    $\begingroup$ Thanks for the direct approach which I did not expect :) $\endgroup$ – mac07 Aug 28 '16 at 6:39
  • 1
    $\begingroup$ The direct approach counts X patterns twice, and does not account + patterns at all. $\endgroup$ – Empy2 Aug 28 '16 at 8:09
  • $\begingroup$ @Michael you are correct $\endgroup$ – David Peterson Aug 28 '16 at 8:25

Firstly ensure that no row/column is vacant.

$3$ ways to place a ball in first row, one row and one column covered (imagine them deleted)
$2$ ways to place a ball in second row, a different row and column covered (imagine them deleted)
$1$ way to place the last ball, so that all rows/columns covered

There are now $2$ balls left, and $6$ places vacant, which can be chosen in $\binom62$ ways

Putting the pieces together, $\;3\cdot 2\cdot 1 \binom62 = 90$


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.