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,2

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.

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).

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

Example

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.

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

Prog

(PARI) Vec(-2*x^4/((x-1)*(x+1)*(2*x-1)*(3*x-1))  + O(x^100)) \\ Colin Barker, Sep 22 2013
(Magma) [(3^n - 2^(n+2) + 6 + (-1)^n) / 12: n in [3..30]]; // Vincenzo Librandi, Sep 23 2013

Crossrefs

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

Sequence in context: A244376 A009338 A261473 * A320526 A193519 A268329

Adjacent sequences: A174392 A174393 A174394 * A174396 A174397 A174398

Keyword

nonn,easy

Author

Patrick Labarque, Mar 18 2010, Mar 21 2010

Extensions

More terms from Colin Barker, Sep 22 2013

Status

approved