0
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .