A307248 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.
1, 3, 43, 1959, 322711, 200353563, 480333970243, 4501677356510799, 166000436233279199791, 24177686356348838326758723, 13944023623713892837664882211163, 31901388234430284116488783907815338999, 289909480221693304736013256104154256737093831
Offset: 1
Keywords
Examples
For n = 3, the simplest solutions are: 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 1 but any of the 0's may also be a 1, e.g.: 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1
Links
- Wikipedia, Logical matrix.
Crossrefs
Cf. A307232.
Formula
a(1) = 1; a(n) = 1 + Sum_{k=1..n-1} 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 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.
Comments