Let $a_{n}$ be the number of ways to fill an $n \times n$ board with the digits 0 and 1, such that the sum in each row and each column is the same. For example, the $2 \times 2$ boards that satisfy this rule are:

| 0 | 0 |
| :--- | :--- |
| 0 | 0 |


| 1 | 0 |
| :--- | :--- |
| 0 | 1 |


| 0 | 1 |
| :--- | :--- |
| 1 | 0 |


| 1 | 1 |
| :--- | :--- |
| 1 | 1 |

Therefore, $a_{2}=4$. Calculate the values of $a_{3}$ and $a_{4}$.
Solution

For $3 \times 3$ boards, we will divide the solution into cases based on the number of 1s per row:

- Case 1: there are no 1s. In this case, we only have one board:

| 0 | 0 | 0 |
| :--- | :--- | :--- |
| 0 | 0 | 0 |
| 0 | 0 | 0 |

- Case 2: we have one 1 per row. In this case, we need to choose one 1 in each row. For the first row, we have 3 choices (each of the cells in this row). Without loss of generality, we can assume we chose the first cell. Note that in the column where this 1 was chosen, we can only have zeros, as the sum in each column must also be 1.

| 1 | 0 | 0 |
| :--- | :--- | :--- |
| 0 | $\star$ | $\star$ |
| 0 | $\star$ | $\star$ |

Now, for the second row, we only have two possible choices (we cannot place two 1s in the same column), while for the last row, we only have one. Therefore, in this case, we have $3 \times 2 \times 1=6$ boards.

- Case 3: now, we see that the number of boards where each row has two 1s is equal to the number of boards with one 1 in each row. This is true because, given a board with two 1s in each row, we just need to swap the zeros for ones and the ones for zeros, and we will obtain a board with only one 1 in each row.
- Case 4: the same applies to the number of boards with only ones, which is equal to the number of boards with only zeros. Therefore,

$$
a_{3}=1+6+6+1=14
$$

To calculate $a_{4}$, we will perform a similar count as in the case of $a_{3}$. If there are no 1s, we only have one board formed by zeros. The same applies if there are no zeros in the board. If we have only one 1 in each row, we just need to do a similar calculation as in the case of $a_{3}$. Thus, we have 4 choices for the first row, 3 choices for the second row (we cannot have two 1s in the same column), 2 choices for the third row, and 1 choice for the last row. Therefore, we have $4 \times 3 \times 2 \times 1=24$ boards with one 1 in each row. The same calculation applies to the case with one zero in each row.

Now, we only need the case where we have two 1s in each row. We then need to place two 1s in the first row. We can do this in

$$
\frac{4 \times 3}{2}=6
$$

ways. Without loss of generality, let's assume the first row is as follows:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- | :--- |
|  |  |  |  |
|  |  |  |  |
|  |  |  |  |

In the first column, there must be another 1, which can be done in three ways:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| $\star$ |  |  |  |
| $\star$ |  |  |  |
| $\star$ |  |  |  |

Again, without loss of generality, we can assume the board is of the form

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 |  |  |  |
| 0 |  |  |  |
| 0 |  |  |  |

Now, we divide into two cases:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 1 |  |  |
| 0 |  |  |  |
| 0 |  |  |  |


| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 0 |  |  |
| 0 |  |  |  |
| 0 |  |  |  |

In the first case above, it is easy to see that we can only complete it in one way, as we already have two 1s in the second column and the second row, so we need to fill them with zeros:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 |

Thus, for this case, we have $6 \times 3$ ways to fill the board, remembering that 6 is the number of ways to place two 1s in the first row and 3 is the number of choices for the position of the other 1 in the first column.

In the second case, we end up with a board of the type:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 0 | $\bullet$ | $\bullet$ |
| 0 | $\star$ |  |  |
| 0 | $\star$ |  |  |

We have 2 ways to choose where the 1 goes in the second row (replacing one of the $\bullet$ above) and 2 ways to choose where the 1 goes in the second column (replacing one of the $\star$ above). Without loss of generality, let's assume we end up with a board of the type:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 0 | 1 | 0 |
| 0 | 1 |  |  |
| 0 | 0 | $\star$ | $\star$ |

Now, the board is determined. Indeed, the two stars above must be 1s, as we need to have two 1s in the last row. Completing from there is easy:

| 1 | 1 | 0 | 0 |
| :--- | :--- | :--- | :--- |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 |

So, in this case, we have 6 choices for the first row, then 3 for the first column. Next, 2 choices for the second row and 2 for the second column. This gives us $6 \times 3 \times 2 \times 2=72$ choices. Therefore, in total, we have

$$
a_{4}=1+24+(72+18)+24+1=140
$$