A174395 The number of different 4-colorings for the vertices of all triangulated planar polygons on a base with n vertices if the colors of two adjacent boundary vertices are fixed.

0, 2, 10, 40, 140, 462, 1470, 4580, 14080, 42922, 130130, 393120, 1184820, 3565382, 10717990, 32197660, 96680360, 290215842, 870997050, 2613690200, 7842468700, 23530202302, 70596199310, 211799782740, 635421717840, 1906309892762, 5719019156770, 17157236427280

Offset: 3

Author

Patrick Labarque, Mar 18 2010, Mar 21 2010

Keywords

• nonn
• easy

Comments

1st: The number of different vertex colorings with 4 or 3 colors for n vertices is: (3^(n-1)-2-(-1)^n)/4.

2nd: The number of 3-colorings is: (2^n -3-(-1)^n)/3.

The above sequence is the difference between the first and the second one.

Examples

			n=3 then a(3)=0 as there are no 4-colorings for the only triangle.
n=4 then a(4)=2 as there are six good colorings less four 3-colorings for the two triangulated quadrilaterals (4-gons).
n=5 then a(5)=10 as there are twenty good colorings less ten 3-colorings for the five triangulated pentagons.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 3..1000
• Index entries for linear recurrences with constant coefficients, signature (5,-5,-5,6).

Crossrefs

Equals A081251 (2,6,20...) minus A026644 (2,4,10...)

Programs

Magma

[(3^n - 2^(n+2) + 6 + (-1)^n) / 12: n in [3..30]]; // Vincenzo Librandi, Sep 23 2013

Mathematica

CoefficientList[Series[-2 x/((x - 1) (x + 1) (2 x - 1) (3 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 23 2013 *)
LinearRecurrence[{5,-5,-5,6},{0,2,10,40},30] (* Harvey P. Dale, Aug 29 2015 *)

PARI

Vec(-2*x^4/((x-1)*(x+1)*(2*x-1)*(3*x-1))  + O(x^100)) \\ Colin Barker, Sep 22 2013

Formula

a(n) = (3^n - 2^(n+2) + 6 + (-1)^n) / 12.

a(n) = 5*a(n-1)-5*a(n-2)-5*a(n-3)+6*a(n-4). G.f.: -2*x^4 / ((x-1)*(x+1)*(2*x-1)*(3*x-1)). - Colin Barker, Sep 22 2013

Extensions

More terms from Colin Barker, Sep 22 2013