Counting no of matrices with exactly n/2 zeros and n/2 ones in each row and each column for a given n

Question

For a blank n * n matrix, even n, we want to assign zeros and ones to this matrix so that each row and each column contains exactly n/2 zeros and n/2 ones for a given n.

Can there be a Dynamic programming method to solve this? I have worked the base case as 0 for a matrix of size 0, then 2 matrices for n = 2. But am not able to get the recursive equation. I was asked this in a recent interview with Microsoft.

Answer 1

You can do anything with dynamic programming - if you are prepared to accept an impractically large state space. In your case, suppose we work in columns from left to right. At step k, we are about to count the number of different ways of filling up the first k columns of the matrix with columns containing n/2 0s and n/2 1s, and we know, for each different state, the number of different ways of filling up the first k-1 columns of the matrix.

What does a state represent? We need it to be detailed enough that, when we have finished, we know that each row contains n/2 0s and n/2 1s. The best I think of is that the state tells us, for each feasible i, the number of rows that have received i 1s so far. So, halfway through a 4x4 matrix, our state might tell us that 2 rows have 2 1s and 2 rows have 0 1s, or, for a different state, that all 4 rows have received a single 1. At the end, we consider only the counts associated with the state that tells us that every row really did receive exactly n/2 1s.

For our 4x4 example, at k = 1 there is only one possible state: 2 rows have received a single 1 and two rows have received a single 0. We could use a backtrack search to work out the possible successor states - 2 rows with 2 1s and 2 rows with 0 1s, 1 row with 2 1s, two with equal splits, and 1 row with no 1s, or 4 rows all with equal splits. Given that, we can work out the number of partial matrices belonging to each state.

This is a dynamic programming solution, but the number different partial counts halfway through working out a large matrix will itself be large, and you can see that the programming is non-trivial. I wonder if there is a better way to do this?