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

%I #86 Oct 14 2024 12:27:35

%S 0,6,6,18,30,66,126,258,510,1026,2046,4098,8190,16386,32766,65538,

%T 131070,262146,524286,1048578,2097150,4194306,8388606,16777218,

%U 33554430,67108866,134217726,268435458,536870910,1073741826,2147483646

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

%C 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?

%C a(n) is also the multiple of six that's nearest to 2^n. - _David Eppstein_, Aug 31 2010

%C 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

%C 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

%H Vincenzo Librandi, <a href="/A092297/b092297.txt">Table of n, a(n) for n = 1..1000</a>

%H K. Böhmová, C. Dalfó, and C. Huemer, <a href="http://upcommons.upc.edu/bitstream/handle/2117/80848/Kautz-subdigraphs.pdf">On cyclic Kautz digraphs</a>, Preprint 2016.

%H Cristina Dalfó, <a href="https://arxiv.org/abs/1709.01882">From subKautz digraphs to cyclic Kautz digraphs</a>, arXiv:1709.01882 [math.CO], 2017.

%H Cristina Dalfó, <a href="https://dx.doi.org/10.1016/j.laa.2017.05.046">The spectra of subKautz and cyclic Kautz digraphs</a>, Linear Algebra and its Applications, 531 (2017), p. 210-219.

%H Fern Gossow, <a href="https://arxiv.org/abs/2410.05678">Lyndon-like cyclic sieving and Gauss congruence</a>, arXiv:2410.05678 [math.CO], 2024. See p. 25.

%H Paul P. Martin and Siti Fatimah Zakaria, <a href="https://doi.org/10.1088/1742-5468/ab2905">Zeros of the 4-state Potts model partition function for the square lattice revisited</a>, J. Stat. Mech. 084003 (2019). eq. (7).

%H Carlos I. Perez-Sanchez, <a href="https://arxiv.org/abs/2401.03705">The Spectral Action on quivers</a>, arXiv:2401.03705 [math.RT], 2024.

%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,2).

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

%F 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

%F a(n) = 6*A001045(n-1). - _R. J. Mathar_, Aug 30 2008

%F a(n) = (-1)^n * a(2-n) * 2^(n-1) for all n in Z. - _Michael Somos_, Oct 25 2014

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

%t nn=28;Drop[CoefficientList[Series[6x^2/(1+x)^2/(1-3x/(1+x)),{x,0,nn}],x],1] (* _Geoffrey Critzer_, Apr 05 2014 *)

%t a[ n_] := 2 (2^(n - 1) + (-1)^n); (* _Michael Somos_, Oct 25 2014 *)

%t 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 *)

%t LinearRecurrence[{1,2},{0,6},40] (* _Harvey P. Dale_, May 21 2024 *)

%o (Magma) [2^n+2*(-1)^n : n in [1..40]]; // _Vincenzo Librandi_, Sep 27 2011

%o (PARI) {a(n) = 2 * (2^(n-1) - (-1)^n)}; /* _Michael Somos_, Oct 25 2014 */

%Y Column k=3 of A106512.

%Y Cf. A001045.

%K nonn,easy

%O 1,2

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