OFFSET
0,6
COMMENTS
A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a k-coloring function for the graph. The chromatic polynomial P(G,k) of a simple graph G gives the number of different k-colorings functions of the graph as a function of k. P(G,k) is a polynomial function of k.
The row polynomials R(n,x) of this triangle are defined to be the sum of the chromatic polynomials of all labeled simple graphs on n vertices: R(n,x) = sum {labeled graphs G on n nodes} P(G,x). An example is given below.
LINKS
Alois P. Heinz, Rows n = 0..77, flattened
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410—414.
R. P. Stanley, Exponential structures
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.
Wikipedia, Graph coloring
FORMULA
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function for the triangle is E(z)^x = Sum_{n >= 0} R(n,x)*z^n/(n!*2^C(n,2)) = 1 + x*z + (-x + 2*x^2)*z^2/(2!*2) + (5*x - 12*x^2 + 8*x^3)*z^3/(3!*2^3) + ....
The row polynomials satisfy the recurrence equation: R(0,x) = 1 and
R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).
In terms of the basis of falling factorial polynomials we have, for n >= 1, R(n,x) = Sum_{k = 1..n} A058843(n,k)*x*(x-1)*...*(x-k+1).
The polynomials R(n,x)/2^comb(n,2) form a sequence of binomial type (see Stanley). Setting D = d/dx, the associated delta operator begins D + D^2/(2!*2) + D^3/(3!*2^3) - D^4/(4!*2^4) + 23*D^5/(5!*2^5) + 559*D^6/(6!*2^6) - ... obtained by series reversion of the formal series D - D^2/(2!*2) + 5*D^3/(3!*2^3) - 79*D^4/(4!*2^4) + 3377*D^5/(5!*2^5) - ... coming from column 1 of the triangle.
Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.
The row polynomials evaluated at k is A322280(n,k). - Geoffrey Critzer, Mar 02 2024
Let k>=1 and let D be a directed acyclic graph with vertices labeled on [n]. Then (-1)^n*R(n,-k) is the number of maps C:[n]->[k] such that for all vertices i,j in [n], if i is directed to j in D then C(i)>=C(j). Cf A003024 (k=1), A339934 (k=2). - Geoffrey Critzer, May 15 2024
EXAMPLE
Triangle begins
n\k.|..0.....1......2.......3......4.......5
= = = = = = = = = = = = = = = = = = = = = = =
.0..|..1
.1..|..0.....1
.2..|..0....-1......2
.3..|..0.....5....-12.......8
.4..|..0...-79....208....-192.....64
.5..|..0..3377..-9520...10240..-5120....1024
...
Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely
(a) o o o (b) o o----o (c) o----o----o
(d) 0
/ \
0---0
with chromatic polynomials x^3, x^2*(x-1), x*(x-1)^2 and (x-1)^3 - (x-1), respectively. Allowing for labeling, there is 1 labeled graph of type (a), 3 labeled graphs of type (b), 3 labeled graphs of type (c) and 1 labeled graph of type (d). Thus the sum of the chromatic polynomials over all labeled graphs on 3 nodes is x^3 + 3*x^2*(x-1) + 3*x*(x-1)^2 + (x-1)^3 - (x-1) = 5*x - 12*x^2 + 8*x^3.
Row 3 of A058843 is [1,12,8]. Thus R(3,x) = x + 12*x*(x-1) + 8*x*(x-1)*(x-2) = 5*x - 12*x^2 + 8*x^3.
MAPLE
R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(R(n)):
seq(T(n), n=0..10); # Alois P. Heinz, May 16 2024
MATHEMATICA
r[0] = 1; r[1] = x; r[n_] := r[n] = x*Sum[ Binomial[n-1, k]*2^(k*(n-k))*(r[k] /. x -> x-1), {k, 0, n-1}]; row[n_] := CoefficientList[ r[n], x]; Table[ row[n], {n, 0, 8}] // Flatten (* Jean-François Alcover, Apr 17 2013 *)
CROSSREFS
KEYWORD
AUTHOR
Peter Bala, Apr 16 2013
STATUS
approved