login
Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.
3

%I #42 May 16 2024 14:51:29

%S 1,0,1,0,-1,2,0,5,-12,8,0,-79,208,-192,64,0,3377,-9520,10240,-5120,

%T 1024,0,-362431,1079744,-1282560,778240,-245760,32768,0,93473345,

%U -291615296,372893696,-255754240,100925440,-22020096,2097152,0,-56272471039,182582658048,-247557029888,185511968768,-84263567360,23488102400,-3758096384,268435456

%N Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.

%C 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.

%C 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.

%H Alois P. Heinz, <a href="/A219765/b219765.txt">Rows n = 0..77, flattened</a>

%H R. C. Read, <a href="https://doi.org/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410—414.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/37.pdf">Exponential structures</a>

%H R. P. Stanley, <a href="https://doi.org/10.1016/j.disc.2006.03.010">Acyclic orientation of graphs</a>, Discrete Math. 5 (1973), 171-178.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Graph_coloring">Graph coloring</a>

%F 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) + ....

%F The row polynomials satisfy the recurrence equation: R(0,x) = 1 and

%F R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).

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

%F 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.

%F Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.

%F The row polynomials evaluated at k is A322280(n,k). - _Geoffrey Critzer_, Mar 02 2024

%F 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

%e Triangle begins

%e n\k.|..0.....1......2.......3......4.......5

%e = = = = = = = = = = = = = = = = = = = = = = =

%e .0..|..1

%e .1..|..0.....1

%e .2..|..0....-1......2

%e .3..|..0.....5....-12.......8

%e .4..|..0...-79....208....-192.....64

%e .5..|..0..3377..-9520...10240..-5120....1024

%e ...

%e Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely

%e (a) o o o (b) o o----o (c) o----o----o

%e (d) 0

%e / \

%e 0---0

%e 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.

%e 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.

%p R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(

%p binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))

%p end:

%p T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(R(n)):

%p seq(T(n), n=0..10); # _Alois P. Heinz_, May 16 2024

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

%Y Cf. A003024 (alt. row sums), A006125 (main diagonal), A095351 (main subdiagonal), A134531 (column 1), A058843, A322280.

%K sign,tabl,easy

%O 0,6

%A _Peter Bala_, Apr 16 2013