login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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 A201173

Adjacent sequences:  A307245 A307246 A307247 * A307249 A307250 A307251

KEYWORD

nonn

AUTHOR

Christopher Cormier, Mar 30 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 7 12:07 EDT 2020. Contains 333305 sequences. (Running on oeis4.)