login
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
1, 3, 43, 1959, 322711, 200353563, 480333970243, 4501677356510799, 166000436233279199791, 24177686356348838326758723, 13944023623713892837664882211163, 31901388234430284116488783907815338999, 289909480221693304736013256104154256737093831
OFFSET
1,2
COMMENTS
This is the number of trivial solutions in A307232, serving as a lower bound.
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.
EXAMPLE
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
CROSSREFS
Cf. A307232.
Sequence in context: A136648 A114337 A317343 * A009720 A300873 A333329
KEYWORD
nonn
AUTHOR
Christopher Cormier, Mar 30 2019
STATUS
approved