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,2

Comments

This is the number of trivial solutions in A307232, serving as a lower bound.

Links

Table of n, a(n) for n=1..13.

Wikipedia, Logical matrix.

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

Adjacent sequences: A307245 A307246 A307247 * A307249 A307250 A307251

Keyword

nonn

Author

Christopher Cormier, Mar 30 2019

Status

approved