login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A146161 a(n) is the number of n X n matrices with entries in {1,2,3} such that all adjacent entries (in the same row or column) differ by 1 or -1. 1
3, 8, 48, 512, 12288, 524288, 50331648, 8589934592, 3298534883328, 2251799813685248, 3458764513820540928, 9444732965739290427392, 58028439341502200385896448, 633825300114114700748351602688 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Let G(n) be the graph whose vertices are sequences of length n with entries in {1,2,3} for which adjacent terms differ by +-1 and {s,t} is an edge if the i-th term of sequence s differs from the i-th term of sequence t by +-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 2*2^A097063(n) if n is odd.

Proof that a(n) = 2^A097063(n) for n even and 2*2^A097063(n) if n is odd, by Max Alekseyev: Suppose that elements of the n X n 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 n X n matrices defined in A146161 is 2*2^(n^2/2)=2^((n^2+2)/2) if n is even, and 2^((n^2+1)/2) + 2^((n^2-1)/2) = 3*2^((n^2-1)/2) if n is odd. The explicit formula for A097063 gives A097063(n) = (n^2+2)/2 for even n, and A097063(n) = (n^2-1)/2 for odd n. So the conjecture is true.

LINKS

Table of n, a(n) for n=1..14.

FORMULA

a(n) = 2^((n^2+2)/2) if n is even, and 3*2^((n^2-1)/2) if n is odd.

EXAMPLE

The a(2)=8 2 X 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.

CROSSREFS

Sequence in context: A291504 A034183 A003216 * A019015 A000862 A194364

Adjacent sequences:  A146158 A146159 A146160 * A146162 A146163 A146164

KEYWORD

nonn

AUTHOR

W. Edwin Clark, Oct 27 2008

EXTENSIONS

Extended by Max Alekseyev, Mar 23 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 19 08:51 EST 2017. Contains 294923 sequences.