|
|
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.
|
|
2
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|