

A179824


Chromatic polynomial of the star graph on 4 vertices (claw graph) and the path graph on 4 vertices.


3



2, 24, 108, 320, 750, 1512, 2744, 4608, 7290, 11000, 15972, 22464, 30758, 41160, 54000, 69632, 88434, 110808, 137180, 168000, 203742, 244904, 292008, 345600, 406250, 474552, 551124, 636608, 731670, 837000, 953312, 1081344, 1221858
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

To generate a Pythagorean triangle one uses (a,b) to get sides b^2a^2, 2*a*b, and a^2+b^2, having a perimeter of 2*b*(a+b). If for a one uses the triangular number n*(n+1)/2 and for b the next triangular number (n+1)*(n+2)/2, the perimeter of the triangle so formed is (n+1)^3 * (n+2), which will give the same results as this sequence starting at the second term.  J. M. Bergot, Apr 01 2012
Define b(0)=0 and b(n)=A179824(n+1) for n > 0. Then b(n) is the number of 4tuples (w,x,y,z) having all terms in {0,...,n} and no two consecutive terms equal.  Clark Kimberling, May 31 2012
Let n points in the plane each become the centers of n1 concentric circles, circles that pass through only one of each of the other points. The maximum number of intersections of these circles is this sequence. [The solution was given by Andrew Weimholt in the Sequence Fans Mailing List]  J. M. Bergot, Mar 10 2014
Both the 'claw graph', a graph with 4 vertices where one vertex is adjacent to the other three, and the path graph on 4 vertices (per Clark Kimberling's comment), have this sequence as their chromatic polynomial, or the number of proper colorings of the graph using at most n colors. This is the standard example of two graphs which are not isomorphic, but which have the same chromatic polynomial.


LINKS

Vincenzo Librandi, Table of n, a(n) for n = 2..1000
Andrew Weimholt, Re: Intersecting circles, SeqFan post Mar 09 2014.
Index entries for linear recurrences with constant coefficients, signature (5,10,10,5,1).


FORMULA

a(n) = n*(n1)^3.  Jaime Soffer (jaime.soffer(AT)gmail.com), Jul 30 2010
G.f.: 2*x^2*(1 + 7*x + 4*x^2)/(1x)^5.  Colin Barker, Jan 30 2012
a(n) = 2*A019582(n).  R. J. Mathar, Jun 09 2013
a(n) = 5*a(n1)  10*a(n2) + 10*a(n3)  5*a(n4) + a(n5).  Vincenzo Librandi, Mar 12 2014


EXAMPLE

From Jack W Grahl, Jul 16 2018: (Start)
Consider the claw graph, which has vertices A, B, C, D, and edges AB, AC, AD. To color this graph with 3 colors, we can choose any of the 3 colors for A. Then each of the other vertices can be colored with any of the remaining two colors, giving 3 * 2 * 2 * 2 = 24 choices in all.
Similarly, consider the path graph with the same vertices and edges AB, BC, CD. We have 3 choices for the color of A, then 2 choices for the color of B (any color except that chosen for A), 2 choices for the color of C (any color except B's) etc. (End)


MATHEMATICA

CoefficientList[Series[2 (1 + 7 x + 4 x^2)/(1  x)^5, {x, 0, 50}], x] (* Vincenzo Librandi, Mar 12 2014 *)
Table[n^3+n^4, {n, 40}] (* or *) LinearRecurrence[{5, 10, 10, 5, 1}, {2, 24, 108, 320, 750}, 40] (* Harvey P. Dale, Sep 05 2015 *)


PROG

(Haskell) let f n = [ (x, a, b, c)  let t = [1..n], x < t, a < t, x /= a, b < t, x /= b, c < t, x /= c ] in map (length.f) [2..]
(Haskell) let f n = n*(n1)^3 in map f [2..]
(PARI) a(n) = n*(n1)^3 \\ Charles R Greathouse IV, Mar 11 2014
(MAGMA) I:=[2, 24, 108, 320, 750]; [n le 5 select I[n] else 5*Self(n1)10*Self(n2)+10*Self(n3)5*Self(n4)+Self(n5): n in [1..50]]; // Vincenzo Librandi, Mar 12 2014


CROSSREFS

Sequence in context: A121199 A009538 A009556 * A034310 A060817 A045820
Adjacent sequences: A179821 A179822 A179823 * A179825 A179826 A179827


KEYWORD

nonn,easy


AUTHOR

Jaime Soffer (jaime.soffer(AT)gmail.com), Jul 28 2010


EXTENSIONS

Name edited by Jack W Grahl, Jul 16 2018


STATUS

approved



