cp's OEIS Frontend

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

%I A219765 #46 May 12 2025 06:46:11
%S A219765 1,0,1,0,-1,2,0,5,-12,8,0,-79,208,-192,64,0,3377,-9520,10240,-5120,
%T A219765 1024,0,-362431,1079744,-1282560,778240,-245760,32768,0,93473345,
%U A219765 -291615296,372893696,-255754240,100925440,-22020096,2097152,0,-56272471039,182582658048,-247557029888,185511968768,-84263567360,23488102400,-3758096384,268435456
%N A219765 Triangle of coefficients of a polynomial sequence related to the coloring of labeled graphs.
%C A219765 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 A219765 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 A219765 Alois P. Heinz, <a href="/A219765/b219765.txt">Rows n = 0..77, flattened</a>
%H A219765 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 A219765 R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/37.pdf">Exponential structures</a>
%H A219765 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 A219765 Wikipedia, <a href="http://en.wikipedia.org/wiki/Graph_coloring">Graph coloring</a>
%F A219765 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 A219765 The row polynomials satisfy the recurrence equation: R(0,x) = 1 and
%F A219765 R(n+1,x) = x*Sum_{k = 0..n} binomial(n,k)*2^(k*(n+1-k))*R(k,x-1).
%F A219765 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 A219765 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 A219765 Alternating row sums A003024. Column 1 = A134531. Main diagonal A006125. Main subdiagonal (-1)*A095351.
%F A219765 The row polynomials evaluated at k is A322280(n,k). - _Geoffrey Critzer_, Mar 02 2024
%F A219765 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 A219765 Triangle begins:
%e A219765   n\k.|..0.....1......2.......3......4.......5
%e A219765   = = = = = = = = = = = = = = = = = = = = = = =
%e A219765   .0..|..1
%e A219765   .1..|..0.....1
%e A219765   .2..|..0....-1......2
%e A219765   .3..|..0.....5....-12.......8
%e A219765   .4..|..0...-79....208....-192.....64
%e A219765   .5..|..0..3377..-9520...10240..-5120....1024
%e A219765   ...
%e A219765 Row 3 = [5, -12, 8]: There are 4 unlabeled graphs on 3 vertices, namely
%e A219765 (a)  o    o    o    (b)  o    o----o    (c)  o----o----o
%e A219765 (d)   0
%e A219765      / \
%e A219765     0---0
%e A219765 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 A219765 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 A219765 R:= proc(n) option remember; `if`(n=0, 1, expand(x*add(
%p A219765       binomial(n-1, k)*2^(k*(n-k))*subs(x=x-1, R(k)), k=0..n-1)))
%p A219765     end:
%p A219765 T:= n-> (p-> seq(coeff(p,x,i), i=0..degree(p)))(R(n)):
%p A219765 seq(T(n), n=0..10);  # _Alois P. Heinz_, May 16 2024
%t A219765 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 A219765 Cf. A003024 (alt. row sums), A006125 (main diagonal), A095351 (main subdiagonal), A134531 (column 1), A058843, A322280.
%K A219765 sign,tabl,easy
%O A219765 0,6
%A A219765 _Peter Bala_, Apr 16 2013