A092297 Number of ways of 3-coloring an annulus consisting of n zones joined like a pearl necklace.

0, 6, 6, 18, 30, 66, 126, 258, 510, 1026, 2046, 4098, 8190, 16386, 32766, 65538, 131070, 262146, 524286, 1048578, 2097150, 4194306, 8388606, 16777218, 33554430, 67108866, 134217726, 268435458, 536870910, 1073741826, 2147483646

Offset: 1

Author

S. B. Step (stepy(AT)vesta.ocn.ne.jp), Feb 06 2004

Keywords

• nonn
• easy

Comments

A circular domain means a domain between two concentric circles and it is divided into n parts by n boundary lines perpendicular to the circles. Both sides of a line must have different colors. How many ways of coloring are there?

a(n) is also the multiple of six that's nearest to 2^n. - David Eppstein, Aug 31 2010

a(n) apparently is the trace of the n-th power of the adjacency matrix of the complete 3-graph, a 3 X 3 matrix with diagonal elements all zero and off-diagonal all ones (cf. A001045). If so, a(n) is the number of closed walks on the graph of length n. - Tom Copeland, Nov 06 2012

For n >= 2, a(n) is the number of length n words on 3 letters with no two consecutive like letters including the first and the last. Cf. A218034. - Geoffrey Critzer, Apr 05 2014

Examples

			a(2)=6 because we can color one zone in 3 colors and the other in 2, so 2*3=6 in all.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
• Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
• Cristina Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), p. 210-219.
• Fern Gossow, Lyndon-like cyclic sieving and Gauss congruence, arXiv:2410.05678 [math.CO], 2024. See p. 25.
• Paul P. Martin and Siti Fatimah Zakaria, Zeros of the 4-state Potts model partition function for the square lattice revisited, J. Stat. Mech. 084003 (2019). eq. (7).
• Carlos I. Perez-Sanchez, The Spectral Action on quivers, arXiv:2401.03705 [math.RT], 2024.
• Index entries for linear recurrences with constant coefficients, signature (1,2).

Crossrefs

Column k=3 of A106512.

Cf. A001045.

Programs

Magma

[2^n+2*(-1)^n : n in [1..40]]; // Vincenzo Librandi, Sep 27 2011

Mathematica

nn=28;Drop[CoefficientList[Series[6x^2/(1+x)^2/(1-3x/(1+x)),{x,0,nn}],x],1] (* Geoffrey Critzer, Apr 05 2014 *)
a[ n_] := 2 (2^(n - 1) + (-1)^n); (* Michael Somos, Oct 25 2014 *)
a[ n_] := If[ n < 1, -(-2)^(n - 1) a[2 - n] , (-1)^n HypergeometricPFQ[ Table[ -2, {k, n}], Table[ 1, {k, n - 1}], 1]] (* Michael Somos, Oct 25 2014 *)
LinearRecurrence[{1,2},{0,6},40] (* Harvey P. Dale, May 21 2024 *)

PARI

{a(n) = 2 * (2^(n-1) - (-1)^n)}; /* Michael Somos, Oct 25 2014 */

Formula

a(n) = 2^n + 2*(-1)^n; recurrence a(1)=0, a(2)=6, a(n) = 2*a(n-2) + a(n-1).

O.g.f: -6*x^2/((1+x)*(2*x-1)) = -3 - 1/(2*x-1) + 2/(1+x). - R. J. Mathar, Dec 02 2007

a(n) = 6*A001045(n-1). - R. J. Mathar, Aug 30 2008

a(n) = (-1)^n * a(2-n) * 2^(n-1) for all n in Z. - Michael Somos, Oct 25 2014