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

[Edwin Clark]

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