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

Edwin Clark eclark at math.usf.edu
Mon Oct 27 19:39:44 CET 2008

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

```