A090860 Number of ways of 4-coloring a map in which there is a central circle surrounded by an annulus divided into n-1 regions. There are n regions in all.

24, 72, 120, 264, 504, 1032, 2040, 4104, 8184, 16392, 32760, 65544, 131064, 262152, 524280, 1048584, 2097144, 4194312, 8388600, 16777224, 33554424, 67108872, 134217720, 268435464, 536870904, 1073741832, 2147483640, 4294967304

Offset: 4

Author

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

Keywords

• nonn

Comments

The number of ways of m-coloring an annulus consisting of n zones joined like a pearl necklace is (m-1)^n + (-1)^n*(m-1), where m >= 3 (cf. A092297 for m=3). Now we must also color the central region.

Examples

			We can choose 4 colors to color the inside zone, therefore b(3)=6 because we can color one zone in the annulus in 3 colors, another in 2, the other in 1, so 3*2*1=6 in all and a(4)=4*6=24. We can also add a(3)=4*3*2=24 to this sequence.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 4..3000
• S. B. Step, More information.
• Index entries for linear recurrences with constant coefficients, signature (1,2).

Crossrefs

Cf. A001045, A092297.

Programs

Magma

[2^(n+1)-8*(-1)^n: n in [4..35]]; // Vincenzo Librandi, Oct 10 2011

Mathematica

LinearRecurrence[{1,2},{24,72},30] (* Harvey P. Dale, Jan 25 2020 *)

Formula

m=4, a(n)=m*((m-2)^(n-1)+(-1)^(n-1)*(m-2)); recurrence m=4, b(1)=0, b(2)=(m-1)*(m-2), b(n)=(m-2)*b(n-2)+(m-3)*b(n-1), a(n)=m*b(n-1).

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

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

a(n) = 2^(n+1) - 8*(-1)^n. - Vincenzo Librandi, Oct 10 2011