# A combination problem of picking m out of n

I am thinking of a problem of putting 4 identical beans onto 4 grids of a 3x3 chessboard. The possible number of selection is $$C(9, 4) = \frac{9!}{4!5!} = 126$$

Now assuming we need to put at least 1 bean on the first column and at least 1 bean on the second column, I want to find out the possible configuration. To solve it, I need to pick 1 spot on the first column and 1 spot on the second column, there will be 3x3 = 9 ways to do it. I then pick another 2 spots out of the remaining 9-2=7 spots for all my 4 beans. The total combination will be $$3 \times 3 \times C(7,2) = 189$$

I do not understand how come this combination is even more than the total combination (126). Any idea what I missed in the calculation? Thanks.

That is because $$\, 3×3 × {7 \choose 2}$$ has duplicates.

For example, take case of choosing cell $$(1,1) \,$$ first column first row as part of $$3$$ selections from column $$1$$.

You again choose them as part of $${7 \choose 2}$$ when you select cell $$(1,2)$$ from the first column.

The easiest way to do this will be to find number of ways to keep column $$1$$ empty = $${6 \choose 2}$$. Similarly for column $$2$$. As both column $$1$$ and $$2$$ cannot be empty at the same time, your answer based on principle of inclusion exclusion is simply

$$= 126 - 2 \times {6 \choose 2} = 96$$.

If there are more than one bean in the first or second columns, that configuration is double-counted (or triple-counted).

To solve this problem, one should consider the complement: the cases when columns 1 or 2 do not contain any beans. There are $$C(6,4) \times 2$$ such cases (they cannot be both empty!) Hence the number of cases where at least 1 bean is on the first column and at least 1 bean is on the second column is $$C(9,4) - 2 \times C(6,4) = 96$$.