Find the total number of ways in which the board can be shaded in a particular way.

Question

Some of the squares of a $3 \times 3$ board are shaded in such a way that in each row and in each column there is at least one black square. We regard symmetries (via rotation or reflection) of the same coloring as distinct, like the pair of shadings below. Find the total number of ways in which the board can be shaded in this way.

---

My thought is to treat the rows and columns separately first, then apply PIE. But I don't know how to carry out this plan. Thanks in advance!

Answer 1

For a rectangular grid of $n$ columns and $m$ rows of squares call the set $\xi$ that of total square shadings, then:

• Any row may be shaded in $2^n$ ways.
• Exactly $1$ of those $2^n$ shadings is empty.
• There are therefore $2^n-1$ non-empty shadings of each of the $m$ rows.
• There are therefore $|\xi|=(2^n-1)^m$ total shadings with no empty rows.

Call $A_k$ the set of shadings of our $n\times m$ rectangle with column $k$ empty, then, deleting row $k$ we have that $|A_k|$ is just the shadings of an $(n-1)\times m$ rectangle

$$|A_k|=(2^{n-1}-1)^m$$

the intersection of any two of these sets is just the shadings of an $(n-2)\times m$ rectangle

$$|A_{k_1}\cap A_{k_2}|=(2^{n-2}-1)^m$$

and so on:

$$|A_{k_1}\cap A_{k_2}\cap A_{k_3}|=(2^{n-3}-1)^m$$ $$\vdots$$ $$|A_{k_1}\cap A_{k_2}\cap \cdots\cap A_{k_{n-1}}|=(2^1-1)^m=1$$ $$|A_1\cap A_2\cap\cdots \cap A_n|=(2^0-1)^m=0$$

Now call

$$S_r=\sum_{k_1\lt k_2\lt\cdots\lt k_r}|A_{k_1}\cap A_{k_2}\cap \cdots\cap A_{k_{r}}|=\binom{n}{r}(2^{n-r}-1)^m$$

The principle of inclusion-exclusion says (setting $\xi\equiv A_0$)

$$|(A_1\cup A_2\cup\cdots \cup A_n)'|=\sum_{r=0}^{n}(-1)^rS_r$$

Hence the general desired count for no empty rows or columns for an $n\times m$ grid is

$$|(A_1\cup A_2\cup\cdots \cup A_n)'|=\sum_{r=0}^{n}(-1)^r\binom{n}{r}(2^{n-r}-1)^m$$

In this case $n=m=3$, then

$$\begin{align}|(A_1\cup A_2\cup A_3)'|&=\binom{n}{0}(2^{3}-1)^3-\binom{n}{1}(2^{2}-1)^3+\binom{n}{2}(2^{1}-1)^3\\&=265\end{align}$$

Answer 2

How many possible shadings are there ($2^9$).

Now subtract off the number of possible shadings in which one row (or column) is known to be "bare" -- six ways to pick the row or column, times $2^6$.

Now add back the number of possible shadings in which two rows (or columns) are known to be "bare", plus the number of possible shadings in which one row and one column are both known to be "bare." (In both situations, the configurations will have been double subtracted in step 2, so you have to add them back.) Two rows/two columns can be chosen in $3+3=6$ ways and each has $2^3$ possible configurations. One row and one column can be chosen in $9$ ways, and each has $2^4$ configurations.

Now subtract back out shadings in which 2 rows and one column (or vice versa), or all three rows or columns are known to be bare. Note that using this automatic remove-add-back technique, you need to consider those two "all bare: cases separately, even though they represent the identical single configuration, because they are going to be added back later. This step subtracts $2\cdot 9 \cdot 2^2 + 2 \cdot 2^0$ configurations.

Now add back shadings in which 3 rows and one column (or vice versa) , or two rows and two columns, are known to be bare:
$2\cdot 3 \cdot 2^0 + 9 \cdot 2^1$.

Now subtrack shadings in which 3 rows and 2 columns (or vice versa) are known to be bare: $2\cdot 3 \cdot 2^0 $.

Finally, add the one configuration in which the whole grid is unshaded.

The total is

$$2^9 - 6\cdot 2^6 +( 6\cdot 2^3 + 9 \cdot 2^4)-(2\cdot 9 \cdot 2^2+2\cdot 2^0)+(2\cdot 3 \cdot 2^1+9\cdot 2^1)-(2\cdot3\cdot 2^0) + 1=271 $$ configurations in which there are no bare rows or columns.

Thete may be some careless errors here but this is the idea.