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

Benoît Jubin benoit.jubin at gmail.com
Mon Oct 27 21:16:05 CET 2008


> How about a formula for the case where the entries are in {1,2,...,k}?

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.

Benoit



On Mon, Oct 27, 2008 at 1:03 PM, Edwin Clark <eclark at math.usf.edu> wrote:
> On Mon, 27 Oct 2008, Max Alekseyev wrote:
>
>> On Mon, Oct 27, 2008 at 11:39 AM, Edwin Clark <eclark at math.usf.edu> wrote:
>>>
>>> I just submitted the following sequence: Perhaps someone can prove
>>> the conjecture.
>>>
>>> %S A146161 3,8,48,512,12288,524288,50331648,8589934592,3298534883328,
>>> %T A146161 2251799813685248,3458764513820540928
>>>
>>> %N A146161 a(n) is the number of n by n matrices with entries in {1,2,3}
>>> such that all adjacent entries (in the same row or column) differ by 1 or
>>> -1.
>>>
>>> %C A146161 Let G(n) be the graph whose vertices are sequences of length n
>>> with entries in {1,2,3} where two sequences s and t are adjacent if for
>>> each i, s(i) and t(i) differ by 1 or -1. Let A be the adjacency matrix of
>>> this graph then a(n) is the sum of the entries in A^(n-1). That is, a(n)
>>> is the number of paths of length n-1 in the graph G(n).
>>
>> It looks like this comment defines a different sequence:
>
> Sorry, you are right.
> I meant to say let G(n) be the graph whose vertices are sequences of
> length n for which adjacent terms diffter by +/1 1 and {s,t} is an edge
> if the ith value of sequence s differs from the ith value of sequence t
> by +/-1.
>
>>
>>> Conjecture: a(n) = 2^A097063(n) for n even and 3*2^A097063(n) if n is odd.
>>
>> Back to the sequence A146161:
>> Suppose that elements of the nxn matrix are colored in black and white
>> like a chessboard. Then either all black or all white elements must
>> equal 2. Each element of the other color can be 1 or 3 independently.
>> For even n, the number of black and white elements is the same and
>> equal n/2. For odd n, the number of black/white squares differs by 1.
>> Therefore, the number of nxn matrices defined in A146161 is
>> 2*2^(n^2/2)=2^((n^2+1)/2) if n is even, and 2^((n^2+1)/2) +
>> 2^((n^2-1)/2) = 3*2^((n^2-1)/2).
>>
>> The explicit formula for A097063 tells that A097063(n)=(n^2+1)/2 for
>> even n, and A097063(n)=(n^2-1)/2 for odd n. So, the conjecture is
>> true.
>>
>> Regards,
>> Max
>>
> Excellent, Max! Thanks! That settles that.
>
>
> How about a formula for the case where the entries are in {1,2,...,k}?
> Do you see a pattern there?
>
> In particular the number of n x n matrices with entries in {1,2,3,4} such
> that adjacent entries differ by +/- 1 is given by: (if I haven't made a
> mistake) for n from 1 to 10.
>
> 4, 14, 126, 2468, 110894, 11197722, 2560257900, 1321295925910,
> 1541096794523414, 4060098102291960100
>
>
> --Edwin
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>




More information about the SeqFan mailing list