
FORMULA

a(1) = 1; a(n) = 1 + Sum_{k=1..n1} binomial(n,k)*(2^(k^2)  a(k)).
Proof: Consider a 1 X 1 matrix. There is 1 solution, so a(1) = 1. Consider a 2 X 2 matrix. There are 2 rows, so there are 2 possibilities. If we have 2 row/column pairs, then we have one solution, a matrix of all 1's, and there are no free positions. If we have only 1 row/column pair, then there is one free position, and there are binomial(2,1) ways to place it. Consider the free position as a 1 X 1 matrix. If this 1 X 1 matrix itself has a row/column pair, then our whole 2 X 2 matrix becomes 1's and we duplicate the case with 2 row/column pairs. Thus there are only 2^(1^2)  a(1) = 1 options for this 1 X 1 free position, a 0. In total there are 1 + 2 = 3 distinct solutions, so a(2) = 3. Consider a 3 X 3 matrix. There are 3 possibilities. If we have 3 row/column pairs, then we have the matrix of all 1's. If we have 2 row/column pairs, then we have one free position. There are binomial(3,1) ways to place it. Again, the only option is 0 or else we duplicate the matrix of all 1's. If we only have 1 row/column pair, then we have four free positions in a 2 X 2 pattern. There are binomial(3,2) ways to place them, and there are 2^(2^2) possible options for the elements. But now, there is more than one choice that leads to duplication. If we choose the 2 X 2 matrix to be all 1's, then the entire 3 X 3 is all 1's and we already considered that. Also, if we choose either of the other 2 solutions to n = 2, then we duplicate the 3 X 3 case with only one free position. So out of all the possibilities for this 2 X 2 matrix of free positions, a(2) = 3 of them lead to duplication. By induction, for an n X n matrix, there are n possibilities for the number of row/column pairs. n row/column pairs is the matrix of all 1's, and then we can consider n1 pairs, n2 pairs, ..., 1 pair, which leads to k^2 free positions, k = 1, 2, ..., n1. Each step adds binomial(n,k)*2^(k^2) possible solutions, but we discount the a(k) solutions that lead to duplicating an earlier case.
