Combinatorics - Number of ways to fill a 3x3 grid with 0's and 1's such that there is at least one zero in each column and row

Question

There seems to be a simple answer for this problem, but I just can't figure it out. I know there must be at least 3-9 zeros for a valid arrangement, and that there are $3!$ (6) possible combinations for 3 zeros yet only 1 combination for 9 zeros. Yet I am stuck on how to calculate the other possibilities.

Answer 1

Dan Uznaski has already counted the number of ways of doing it with $6$ to $8$ zeros in a comment, leaving the cases of $4$ or $5$ zeros.

With $4$ zeros, there will be one row and one column with two zeros each. There are $3\cdot3=9$ ways to choose them. Then there is $1$ arrangement in which their intersection has a one, and otherwise there are $2\cdot2=4$ ways to place the zeros in them, fixing the position of the fourth zero, for a total of $9(1+4)=45$.

For $5$ zeros, continuing in the spirit of Dan's count for $6$ zeros, there are $4$ ones, and to fail, three of them must be in exactly one row or one column. There are $6$ choices, and then in each case $6$ choices where to place the fourth one, so $6\cdot6=36$ arrangements out of $\binom95=126$ fail, leaving $90$.

Putting it all together, including your results and Dan's, we get

$$6+45+90+78+36+9+1=265$$

valid arrangements, in agreement with Brian's result from the answer that Chris Culter linked to in a comment:

$$ \sum_{k=0}^3\binom3k(-1)^k\left(2^{3-k}-1\right)^3=343-81+3=265\;. $$

Answer 2

This is an alternate approach, which admittedly is more complicated than joriki's answer and Brian's result:

Let S be the set of all ways to fill these matrices, and

let $A_i$ for $1\le i\le3$ be the set of matrices with all 1's in row $i$, and

let $A_i$ for $4\le i\le 6$ be the set of matrices with all 1's in column $i-3$.

Then $\big|\overline{A_1}\cap\cdots\cap\overline{A_6}\big|=\big|S\big|-\sum\big|A_i\big|+\sum\big|A_i\cap A_j\big|-\sum\big|A_i\cap A_j\cap A_k\big|+\cdots+\big|A_1\cap\cdots\cap A_6\big|$

$\displaystyle=2^9-6(2^6)+[3(2^3)+3(2^3)+3(3)(2^4)]-[2(1)+2(3)(3)(2^2)]+[6(1)+3(3)(2^1)]-6(1)+1(1)$

$=265$.