[seqfan] Re: n x n matrices with adjacent entries differing by +/- 1

Edwin Clark eclark at math.usf.edu
Sun Nov 2 14:46:58 CET 2008


Très bien, Benoît! Of course one needs to do a little work to see that the 
mapping A -> A mod 3 is a surjection as well as an injection.

The same argument should work if we consider any connected graph instead
the  n by n grid graph which corresponds to the matrix case. That is, the 
number of 3 colorings of a connected graph with the color of one vertex 
fixed is the same as the number of ways to label the vertices with integers
so that one vertex is 0 and the labels for adjacent vertices differ by +/- 1.
Sounds like something that graph theorists should be aware of.

Edwin


  On Sat, 1 Nov 2008, Benoît Jubin wrote:

> They are actually the same: let us call the three colors 0,1,2, and
> suppose the upper-left color is 0 (the 1/3 in the definition).
>
> There is a bijection between  the set of matrices with entries in Z,
> upper-left entry 0 and adjacent entries differing by +/-1, and the set
> of 3-colored matrices with upper-left being 0: it is simply "modulo
> 3". Indeed, the constraints correspond under this function between
> sets of matrices: for the coloring, the constraint is that the
> difference between adjacent entries is +/-1 in Z/3Z, and injectivity
> comes from the fact that 3>2.
>
> Benoit
>
>
>
> 2008/11/1 Edwin Clark <eclark at math.usf.edu>:
>> On Mon, 27 Oct 2008, Benoît Jubin wrote:
>>>
>>> It would also be interesting to consider the entries of the matrix in
>>> Z/kZ (that is, 1 and k would also differ by 1). And also the same
>>> sequence for entries in Z or N, the upper-left term being 0.
>>>
>>
>> I computed for n = 1 to 8 the number of n x n matrices with entries in Z,
>> the upper left entry = 0, and adjacent entries (in the same row or column)
>> differing by +/- 1. I got the following:
>>
>> 1, 6, 82, 2604, 193662, 33865632, 13956665236, 13574876544396
>>
>> This  matches the first 8 terms of
>>
>>  http://www.research.att.com/~njas/sequences/A068253
>>
>> which is defined as:
>>
>>  1/3 of the number of colorings of an n X n square array with 3 colors
>>
>> It is too much to imagine the sequences are different, yet I also cannot
>> imagine they coincide by looking at the definitions. Does anyone see a
>> connection?
>>
>> --Edwin
>>
>>
>> _______________________________________________
>>
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list