|
%I #15 Jun 23 2019 17:02:02
%S 1,3,43,1959,322711,200353563,480333970243,4501677356510799,
%T 166000436233279199791,24177686356348838326758723,
%U 13944023623713892837664882211163,31901388234430284116488783907815338999,289909480221693304736013256104154256737093831
%N a(n) is the number of n X n binary matrices (over the reals) with at least one row and column full of 1's where the row index equals the column index.
%C This is the number of trivial solutions in A307232, serving as a lower bound.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Logical_matrix">Logical matrix</a>.
%F a(1) = 1; a(n) = 1 + Sum_{k=1..n-1} binomial(n,k)*(2^(k^2) - a(k)).
%F 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 n-1 pairs, n-2 pairs, ..., 1 pair, which leads to k^2 free positions, k = 1, 2, ..., n-1. 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.
%e For n = 3, the simplest solutions are:
%e 1 1 1 0 1 0 0 0 1
%e 1 0 0 1 1 1 0 0 1
%e 1 0 0 0 1 0 1 1 1
%e but any of the 0's may also be a 1, e.g.:
%e 1 1 1 0 0 1 1 1 1
%e 1 1 0 0 1 1 1 1 1
%e 1 1 0 1 1 1 1 1 1
%Y Cf. A307232.
%K nonn
%O 1,2
%A _Christopher Cormier_, Mar 30 2019
|
