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

[Edwin Clark]

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).

Conjecture: a(n) = 2^A097063(n) for n even and 3*2^A097063(n) if n is odd.

%e A146161 The a(2)=8 2 by 2 matrices with the desired property are {[[1, 
2], [2, 1]], [[1, 2], [2, 3]], [[2, 1], [1, 2]], [[2, 1], [3, 2]], [[2, 
3], [1, 2]], [[2, 3], [3, 2]], [[3, 2], [2, 1]], [[3, 2], [2, 3]]}. Here a 
matrix is represented as a list of its rows.