1,1

For each n we define an undirected labeled graph (with self loops), where the vertices are labeled with strings from {0,1}^n, and there is an edge between two vertices exactly when we can form a 2 X n rectangle whose rows are the two labels, and the 2 X n rectangle has no monochromatic 2 X 2 subsquares. a(n) is the number of walks of length n in this graph. Thus it is the sum of all of the entries of A^n, where A is the adjacency matrix of the graph.

a(2) = 14 because 2 of the 16 colorings are monochromatic

Cf. A055099.

Sequence in context: A034834 A034912 A035018 this_sequence A090598 A060075 A035273

Adjacent sequences: A133127 A133128 A133129 this_sequence A133131 A133132 A133133

nonn

Victor S. MIller (victor(AT)idaccr.org), Sep 19 2007