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

[Max Alekseyev]

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:
Let b(n) be the number of sequences of {1,2,3} of length n such that
every two concecutive elements differ by +/-1.
Then b(n) = 2^floor(n/2) + 2^ceil(n/2) and a(n) = b(n-1)^n.
For even n, we have b(n-1) = 3*2^((n-2)/2) and a(n) = 3^n * 2^(n*(n-2)/2);
while for odd n, b(n-1) = 2^((n+1)/2) and a(n) = 2^(n(n+1)/2).

In particular, for n=2 the above comment gives a(2) = 3^2 = 9 that
enumerates the following paths of length 1 (i.e., single vertices) in
G(2):
11, 12, 13, 21, 22, 23, 31, 32, 33.
This contradicts to the value A146161(2)=8.

> 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