[seqfan] Re: Unique Products Regarding Binary Matrices

hv at crypt.org hv at crypt.org
Fri Jun 11 15:49:31 CEST 2010


Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
:I'm actually most interested in the 9-by-9 case.
:
:I am wondering if it would make a good puzzle, trying to come up with a solution by hand.
:
:But I don't even know if it is possible, although I highly suspect that it is.
:
:Thanks,
:Leroy Quet
:
:
:
:[ ( [ ([( [ ( ([[o0Oo0Ooo0Oo(0)oO0ooO0oO0o]]) ) ] )]) ] ) ]
:
:
:--- On Thu, 6/10/10, Leroy Quet <q1qq2qqq3qqqq at yahoo.com> wrote:
:
:> From: Leroy Quet <q1qq2qqq3qqqq at yahoo.com>
:> Subject: [seqfan]  Unique Products Regarding Binary Matrices
:> To: seqfan at seqfan.eu
:> Date: Thursday, June 10, 2010, 11:24 AM
:> Say we have an n-by-n binary matrix
:> (all elements either 0 or 1).
:> 
:> For a given row of the matrix, take the lengths of the runs
:> of 0's and 1's and multiply these lengths. 
:> (By "run", it is meant a string of consecutive elements in
:> the row (or column) all of the same value b, bounded by the
:> value 1-b or by the edge of the row (or column).)
:> 
:> Do this for all rows and all columns to get 2n products.
:> 
:> Let a(n) = the number of such n-by-n binary matrices such
:> that the 2n products are all unique.
:> 
:> I know that a(n) = 0 for n <= 8, since A034891(n) <
:> 2n for n <= 8.
:> 
:> Is {a(n)} in the EIS already? It would seem a bad idea to
:> compute this sequence via brute-force search of all the
:> 2^(n^2) matrices for a given n, since the number of
:> potential matrices grows so quickly as n grows.

I'm not at all sure what you're asking for here, but for each interpretation
I can imagine:

Let A be any such matrix; define B: B_{i,j} = 1 - A_{i,j}.

Then I think each of the 2n products for B is the same as the corresponding
product for A, so A is not unique.

Hugo




More information about the SeqFan mailing list