# Choosing squares from a grid so that no two chosen squares are in the same row or column

How many ways can 3 squares be chosen from a 5x5 grid so that no two chosen squares are in the same row or column?

Why is this not simply $\binom{5}{3}\cdot\binom{5}{3}$?

I figured that there were $\binom{5}{3}$ ways to choose $3$ different "$x$-axis" coordinates and then same for the "$y$-axis". Thus I would multiply them.

Thanks

-

I would say the first square can be in any of five columns and any of five rows, etc, leading to $5^2\times 4^2 \times 3^2$ but the squares can be any any order so divide by $3!$ to give $$\frac{5^2\times 4^2 \times 3^2}{3!} = 600$$ which is six times as big as $100={5 \choose 3}\times {5 \choose 3}$.

I think your method chooses three rows from five and three columns from five. But there are still six different ways of placing the three squares within the nine squares your choices identify, such that none are in the same row or column.

-
Ohh I understand after you edited your explanation. Thanks! – Matt May 15 '12 at 23:24

Here's the hard way to do the problem: inclusion-exclusion.

There are $25\choose3$ ways to choose 3 squares from the 25.

Now you have to subtract the ways that have two squares in the same row or column. There are 10 ways to choose the row/column, $5\choose2$ ways to choose the two squares in the row/column, and 23 choices remaining for the third square, so all up you must subtract $10\times{5\choose2}\times23$.

Now you have to put back in all the configurations you subtracted out twice. These are the ones with two in the same row and two in the same column, of which there are $25\times4\times4$, and also the ones in which there are three in the same row/column, of which there are $10\times{5\choose3}$. The ones with 3 in a column were counted in once, then subtracted out 3 times, so they have to be put back in twice.

So the answer is $${25\choose3}-10\times{5\choose2}\times23+25\times4\times4+2\times10\times{5\choose3}$$ which comes out to 600.

-

You can choose the first square arbitrarily, so there are $25$ options for it.

There are now $4$ rows and $4$ columns that the second square can be chosen from, so there are $16$ options for it (alternatively, if one just wants to count, there are $25$ squares total, minus the chosen first square, minus the $4$ other squares in the same row, minus the other $4$ squares in the same column, for $25 - 1 - 4 - 4 = 16$ options).

Similarly, there are $9$ options for the third square.

Dividing by $3!$ to account for the fact that the same three squares can be chosen in that many ways, the correct answer is $$\frac{25\cdot 16\cdot 9}{3!} = 600$$ not $$\binom{5}{3}\cdot\binom{5}{3}=10\cdot 10=100.$$

-
@Henry, Andre: Ah, thanks for catching that. – Zev Chonoles May 15 '12 at 23:25