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.
3*a(n) is the number of ternary strings of length n with a positive even number of 0's, a positive even number of 1's and no restriction on the number of 2's (see Example). - Enrique Navarrete, May 14 2026
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
E.g.f.: (1/3) * (cosh(x) - 1)^2 * exp(x). - Enrique Navarrete, May 14 2026
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.
For example, for n=6, the 3*a(6)=120 strings are the 15 permutations of 000011, the 15 permutations of 001111 and the 90 permutations of 001122. - Enrique Navarrete, May 14 2026
MATHEMATICA
CoefficientList[Series[-2 x/((x - 1) (x + 1) (2 x - 1) (3 x - 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Sep 23 2013 *)
(* Alternative: *)
LinearRecurrence[{5, -5, -5, 6}, {0, 2, 10, 40}, 30] (* Harvey P. Dale, Aug 29 2015 *)
PROG
(PARI) concat([0], Vec(-2*x^4/((x-1)*(x+1)*(2*x-1)*(3*x-1)) + O(x^40))) \\ 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
Patrick Labarque, Mar 18 2010, Mar 21 2010
EXTENSIONS
More terms from Colin Barker, Sep 22 2013
STATUS
approved