A339934 -id:A339934 - cp's OEIS frontend

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

1, 0, 1, 0, -1, 2, 0, 5, -12, 8, 0, -79, 208, -192, 64, 0, 3377, -9520, 10240, -5120, 1024, 0, -362431, 1079744, -1282560, 778240, -245760, 32768, 0, 93473345, -291615296, 372893696, -255754240, 100925440, -22020096, 2097152, 0, -56272471039, 182582658048, -247557029888, 185511968768, -84263567360, 23488102400, -3758096384, 268435456

Offset: 0

Peter Bala, Apr 16 2013

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.

			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.

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

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

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

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

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

A380336 Triangular array read by rows. T(n,k) is the number of ways to choose a size k subset S of [n] and form a labeled acyclic digraph on S. Then form another labeled acyclic digraph on [n]-S. For each pair u in S and v in [n]-S add the directed edge u->v or not, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 1, 3, 4, 3, 25, 36, 36, 25, 543, 800, 864, 800, 543, 29281, 43440, 48000, 48000, 43440, 29281, 3781503, 5621952, 6255360, 6400000, 6255360, 5621952, 3781503, 1138779265, 1694113344, 1888975872, 1946112000, 1946112000, 1888975872, 1694113344, 1138779265

Offset: 0

Geoffrey Critzer, Jan 21 2025

			Triangle T(n,k) begins:
     1;
     1,     1;
     3,     4,     3;
    25,    36,    36,    25;
   543,   800,   864,   800,   543;
 29281, 43440, 48000, 48000, 43440, 29281;
 ...

E. de Panafieu and S. Dovgal, Symbolic method and directed graph enumeration, arXiv:1903.09454 [math.CO], 2019.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A339934 (row sums), A003024 (column k=0 and main diagonal).

nn = 6; B[n_] := n! 2^Binomial[n, 2]; e[z_] := Sum[z^n/B[n], {n, 0, nn}]; Map[Select[#, # > 0 &] &,Table[B[n], {n, 0, nn}] CoefficientList[Series[1/e[-u z]*1/e[-z], {z, 0, nn}], {z, u}]] // Grid

Sum_{n>=0} T(n,k)*y^k*x^n/(2^binomial(n,2)*n!) = 1/E(-y*x)*1/E(-x) where E(x) = Sum_{n>=0} x^n/(2^binomial(n,2)*n!).

T(n,k) = binomial(n,k)*A003024(k)*A003024(n-k)*2^(k*(n-k)). - Alois P. Heinz, Jan 22 2025

A340798 Square array read by descending antidiagonals. Let G be a simple labeled graph on n nodes. T(n,k) is the number of ways to give G an acyclic orientation and a coloring function C:V(G) -> {1,2,...,k} so that u->v implies C(u) >= C(v) for all u,v in V(G), n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 10, 25, 0, 1, 4, 21, 122, 543, 0, 1, 5, 36, 339, 3550, 29281, 0, 1, 6, 55, 724, 12477, 241442, 3781503, 0, 1, 7, 78, 1325, 32316, 1035843, 37717630, 1138779265, 0

Offset: 0

Geoffrey Critzer, Jan 21 2021

			Array begins
  1,     1,      1,       1,       1,       1, ...
  0,     1,      2,       3,       4,       5, ...
  0,     3,     10,      21,      36,      55, ...
  0,    25,    122,     339,     724,    1325, ...
  0,   543,   3550,   12477,   32316,   69595, ...
  0, 29281, 241442, 1035843, 3180484, 7934885, ...
  ...

R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A003024 (column k=1), A339934 (column k=2), A322280, A219765.

nn = 6; e[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Prepend[Table[Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[
      Series[1/e[-x]^k, {x, 0, nn}], x], {k, 1, nn}],PadRight[{1}, nn + 1]] // Transpose // Grid

Let E(x) = Sum_{n>=0} x^n/(n!*2^binomial(n,2)). Then Sum_{n>=0} T(n,k)*x^n/(n!*2^binomial(n,2)) = 1/E(-x)^k.

T(n,k) = (-1)^n p_n(-k) where p_n is the n-th polynomial described in A219765.

A342113 Number of surjective compatible pairs (C,O), where O is an acyclic orientation of simple labeled graph G on n nodes and C:V(G) -> {1,2,...}.

Original entry on oeis.org

1, 1, 7, 145, 7999, 1103041, 365051647, 281898887425, 497570152386559, 1976049386530790401, 17439288184770966867967, 338596445913833207323643905, 14343481992486219718322674565119

Offset: 0

Geoffrey Critzer, Feb 28 2021

nonn

A pair (C,O) is a surjective compatible pair if O is an acyclic orientation of the edges of a simple labeled graph G on n nodes, and C is a surjective function from V(G)->{1,2,...k} for some positive integer k such that for all u,v in V(G) if u->v under the orientation then C(u)>= C(v).

R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178.

Cf. A339934.

nn = 12; b[n_] := q^Binomial[n, 2] n! /. q -> 2; e[z_] := Sum[z^n/b[n], {n, 0, nn}];Table[b[n], {n, 0, nn}] CoefficientList[ Series[1/(1 - (1/e[-z] - 1)), {z, 0, nn}], z]

Let E(x) = Sum_{n>=0}x^n/(n! 2^Binomial(n,2)). Then Sum_{n>=0}a_n x^n/(n! 2^Binomial(n,2)) = 1/(2 - E(-x)^-1).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A380336 Triangular array read by rows. T(n,k) is the number of ways to choose a size k subset S of [n] and form a labeled acyclic digraph on S. Then form another labeled acyclic digraph on [n]-S. For each pair u in S and v in [n]-S add the directed edge u->v or not, n>=0, 0<=k<=n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A340798 Square array read by descending antidiagonals. Let G be a simple labeled graph on n nodes. T(n,k) is the number of ways to give G an acyclic orientation and a coloring function C:V(G) -> {1,2,...,k} so that u->v implies C(u) >= C(v) for all u,v in V(G), n >= 0, k >= 0.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A342113 Number of surjective compatible pairs (C,O), where O is an acyclic orientation of simple labeled graph G on n nodes and C:V(G) -> {1,2,...}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula