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

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

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: A247033 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 May 25 21:22 EDT 2017. Contains 287059 sequences.