A322280 -id:A322280 - cp's OEIS frontend

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

1, 2, 6, 26, 162, 1442, 18306, 330626, 8488962, 309465602, 16011372546, 1174870185986, 122233833963522, 18023122242478082, 3765668654914699266, 1114515608405262434306, 467221312005126294077442, 277362415313453291571118082, 233150477220213193598856331266

Offset: 0

N. J. A. Sloane

Row sums of A111636. - Peter Bala, Sep 30 2012
Column 2 of Table 2 in Read. - Peter Bala, Apr 11 2013
It appears that 5 does not divide a(n), that a(n) is even for n>0, that 3 divides a(2n) for n>0, that 7 divides a(6n+5), and that 13 divides a(12n+3). - Ralf Stephan, May 18 2013

			For n=2, {1,2 black, not connected}, {1,2 white, not connected}, {1 black, 2 white, not connected}, {1 black, 2 white, connected}, {1 white, 2 black, not connected}, {1 white, 2 black, connected}.
G.f. = 1 + 2*x + 6*x^2 + 26*x^3 + 162*x^4 + 1442*x^5 + 18306*x^6 + ...

H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 79, Eq. 3.11.2.

T. D. Noe, Table of n, a(n) for n = 0..50
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
S. R. Finch, Bipartite, k-colorable and k-colored graphs
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
A. Gainer-Dewar and I. M. Gessel, Enumeration of bipartite graphs and bipartite blocks, arXiv:1304.0139 [math.CO], 2013.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Martin Svatoš, Peter Jung, Jan Tóth, Yuyi Wang, and Ondřej Kuželka, On Discovering Interesting Combinatorial Integer Sequences, arXiv:2302.04606 [cs.LO], 2023, p. 17.
Eric Weisstein's World of Mathematics, k-Colorable Graph
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

Column k=2 of A322280.
Cf. A135079 (variant).
Cf. A000683, A001831, A002031, A033995, A047864, A052332, A111636, A191371, A223887.

A047863:= func< n | (&+[Binomial(n,k)*2^(k*(n-k)): k in [0..n]]) >;
[A047863(n): n in [0..40]]; // G. C. Greubel, Nov 03 2024

Table[Sum[Binomial[n,k]2^(k(n-k)),{k,0,n}],{n,0,20}] (* Harvey P. Dale, May 09 2012 *)
nmax = 20; CoefficientList[Series[Sum[E^(2^k*x)*x^k/k!, {k, 0, nmax}], {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jun 05 2019 *)

{a(n)=n!*polcoeff(sum(k=0,n,exp(2^k*x +x*O(x^n))*x^k/k!),n)} \\ Paul D. Hanna, Nov 27 2007

{a(n)=polcoeff(sum(k=0, n, x^k/(1-2^k*x +x*O(x^n))^(k+1)), n)} \\ Paul D. Hanna, Mar 08 2008

N=66; x='x+O('x^N); egf = sum(n=0, N, exp(2^n*x)*x^n/n!);
Vec(serlaplace(egf))  \\ Joerg Arndt, May 04 2013

from sympy import binomial
def a(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

def A047863(n): return sum(binomial(n,k)*2^(k*(n-k)) for k in range(n+1))
[A047863(n) for n in range(41)] # G. C. Greubel, Nov 03 2024

a(n) = Sum_{k=0..n} binomial(n, k)*2^(k*(n-k)).
a(n) = 4 * A000683(n) + 2. - Vladeta Jovovic, Feb 02 2000
E.g.f.: Sum_{n>=0} exp(2^n*x)*x^n/n!. - Paul D. Hanna, Nov 27 2007
O.g.f.: Sum_{n>=0} x^n/(1 - 2^n*x)^(n+1). - Paul D. Hanna, Mar 08 2008
From Peter Bala, Apr 11 2013: (Start)
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function is E(x)^2 = 1 + 2*x + 6*x^2/(2!*2) + 26*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Stanley). For other examples see A191371 (k = 3) and A223887 (k = 4).
If A(x) = 1 + 2*x + 6*x^2/2! + 26*x^3/3! + ... denotes the e.g.f. for this sequence then sqrt(A(x)) = 1 + x + 2*x^2/2! + 7*x^3/3! + ... is the e.g.f. for A047864, which counts labeled 2-colorable graphs. (End)
a(n) ~ c * 2^(n^2/4+n+1/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = EllipticTheta[3, 0, 1/2] = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = EllipticTheta[2, 0, 1/2] = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013

Better description from Christian G. Bower, Dec 15 1999

A191371 Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color.

Original entry on oeis.org

1, 3, 15, 123, 1635, 35043, 1206915, 66622083, 5884188675, 830476531203, 187106645932035, 67241729173555203, 38521811621470420995, 35161184767296890265603, 51112793797110111859802115, 118291368253025368001553530883, 435713124846749574718274002747395, 2553666761436949125065383836043837443

Offset: 0

Geoffrey Critzer, Jun 01 2011

Cf. A213442, which counts colorings of labeled graphs on n vertices using exactly 3 colors. For 3-colorable labeled graphs on n vertices see A076315. - Peter Bala, Apr 12 2013

			a(2) = 15: There are two labeled 3-colorable graphs on 2 nodes, namely
A)  1    2   B)  1    2
    o    o       o----o
Using 3 colors there are 9 ways to color the graph of type A and 3*2 = 6 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 15 labeled 3-colored graphs on 2 vertices.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973, 16-18.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Steven R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Column k=3 of A322280.

Cf. A047863. A000685, A076315, A223887.

f[{k_,r_,m_}]:= Binomial[m+r+k,k] Binomial[m+r,r] 2^ (k r + k m + r m); Table[Total[Map[f,Compositions[n,3]]],{n,0,20}]

seq(n)={my(p=(sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))^3); Vecrev(sum(j=0, n, j!*2^binomial(j,2)*polcoef(p,j)*x^j))} \\ Andrew Howroyd, Dec 03 2018

from sympy import binomial
def a047863(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)])
def a(n): return sum([binomial(n, k)*2**(k*(n - k))*a047863(k) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

a(n) = Sum(C(n,k)*C(n-k,r)*2^(k*r+k*m+r*m)) where the sum is taken over all nonnegative solutions to k + r + m = n.
From Peter Bala, Apr 12 2013: (Start)
a(n) = Sum_{k = 0..n} binomial(n,k)*2^(k*(n-k))*A047863(k).
a(n) = 3*A000685(n) for n >= 1.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^3 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 15*x^2/(2!*2) + 123*x^3/(3!*2^3) + 1635*x^4/(4!*2^6) + ....
In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Read). For other examples see A047863 (k = 2) and A223887 (k = 4). (End)

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Original entry on oeis.org

1, 1, 5, 73, 2849, 277921, 65067905, 35545840513, 44384640206849, 124697899490480641, 778525887500557625345, 10693248499002776513697793, 320453350845793018626300755969, 20807125028666778079876193487790081, 2909872870574162514727072641529432735745

Offset: 0

Geoffrey Critzer, Apr 21 2020

nonn

Also 1 together with the row sums of A046860.

A binary relation R on [n] is periodic iff there is a d>=2 such that R^d = R. Let A be the class of non-arcless strongly connected periodic relations (A000629). Then a(n) is the number of binary relations on [n] whose strongly connected components are in A. - Geoffrey Critzer, Dec 12 2023

Alois P. Heinz, Table of n, a(n) for n = 0..77

Cf. A046860, A322280, A011266, A361560, A003024, A365534, A365590.

b:= proc(n, k) option remember; `if`([n, k]=[0$2], 1,
      add(binomial(n, r)*2^(r*(n-r))*b(r, k-1), r=0..n-1))
    end:
a:= n-> add(b(n,k), k=0..n):
seq(a(n), n=0..15);  # Alois P. Heinz, Apr 21 2020

nn = 15; e2[x_] := Sum[x^n/(n! 2^Binomial[n, 2]), {n, 0, nn}];
Table[n! 2^Binomial[n, 2], {n, 0, nn}] CoefficientList[Series[1/(1 - (e2[x] - 1)), {x, 0, nn}], x]

Sum_{n>=0} a_n*x^n/(n!*2^C(n,2)) = 1/(2-Sum_{n>=0} x^n/(n!*2^C(n,2))).

A223887 Number of 4-colored labeled graphs on n vertices.

Original entry on oeis.org

1, 4, 28, 340, 7108, 254404, 15531268, 1613235460, 284556079108, 85107970698244, 43112647751430148, 36955277740855136260, 53562598422461559373828, 131186989945696839128432644, 542676256323680030599454982148

Offset: 0

Peter Bala, Apr 10 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 coloring function for the graph.
A k-colored graph is a k-colorable graph together with its coloring function. This sequence gives the number of labeled 4-colored graphs on n vertices. An example is given below.
See A047863 for labeled 2-colored graphs on n vertices and A191371 for labeled 3-colored graphs on n vertices. See A076316 for labeled 4-colorable graphs on n vertices and A224068 for the count of labeled graphs colored using exactly 4 colors.

			a(2) = 28: There are two labeled 4-colorable graphs on 2 nodes, namely
A)  1    2  B)  1    2
    o    o      o----o
Using 4 colors there are 16 ways to color the graph of type A and 4*3 = 12 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 28 labeled 4-colored graphs on 2 vertices.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Steven R. Finch, Bipartite, k-colorable and k-colored graphs
Steven R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Column k=4 of A322280.

Equals 4 * A000686, A047863 (labeled 2-colored graphs), A076316, A191371 (labeled 3-colored graphs), A224068.

N=66;  x='x+O('x^N);
E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
tgf=E^4;  v=concat(Vec(tgf));
v=vector(#v, n, v[n] * (n-1)! * 2^((n-1)*(n-2)/2) )
/* Joerg Arndt, Apr 10 2013 */

a(n) = sum {k = 0..n} binomial(n,k)*2^(k*(n-k))*b(k)*b(n-k), where b(n) := sum {k = 0..n} binomial(n,k)*2^(k*(n-k)).

Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^4 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 4*x + 28*x^2/(2!*2) + 340*x^3/(3!*2^3) + .... In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Stanley).

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 6, 6, 0, 0, 1, 5, 12, 42, 38, 0, 0, 1, 6, 20, 132, 618, 390, 0, 0, 1, 7, 30, 300, 3156, 15990, 6062, 0, 0, 1, 8, 42, 570, 9980, 136980, 668526, 134526, 0, 0, 1, 9, 56, 966, 24330, 616260, 10015092, 43558242, 4172198, 0, 0

Offset: 0

Andrew Howroyd, Dec 01 2018

Not all colors need to be used.

			Array begins:
===============================================================
n\k| 0 1      2        3          4           5           6
---+-----------------------------------------------------------
0  | 1 1      1        1          1           1           1 ...
1  | 0 1      2        3          4           5           6 ...
2  | 0 0      2        6         12          20          30 ...
3  | 0 0      6       42        132         300         570 ...
4  | 0 0     38      618       3156        9980       24330 ...
5  | 0 0    390    15990     136980      616260     1956810 ...
6  | 0 0   6062   668526   10015092    65814020   277164210 ...
7  | 0 0 134526 43558242 1199364852 11878194300 67774951650 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Columns k=2..5 are A002027, A002028, A002029, A002030.

Cf. A058843, A058875, A322278, A322280.

M(n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=Mat(vector(n, k, Col(serlaplace(1 + log(serconvol(q, p^k)))))));
  matconcat([1, W]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

k-th column is the logarithmic transform of the k-th column of A322280.

E.g.f of k-th column: 1 + log(Sum_{n>=0} A322280(n,k)*x^n/n!).

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

1, 0, 1, 0, 3, 4, 0, 19, 84, 38, 0, 195, 2470, 3140, 728, 0, 3031, 108390, 307390, 186360, 26704, 0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256, 0, 2086099, 726782784, 9030799218, 20784069600, 14401134944, 3463311488, 251548592

Offset: 1

Andrew Howroyd, Dec 01 2018

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with k parts. See A322064 for the definition of stable partition.

			Triangle begins:
  1;
  0,     1;
  0,     3,       4;
  0,    19,      84,       38;
  0,   195,    2470,     3140,      728;
  0,  3031,  108390,   307390,   186360,    26704;
  0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A322064.
Columns k=2..4 are A001832(for n > 1), A322330, A322331.
Right diagonal is A001187.
Cf. A058843, A058875, A322279, A322280.

M(n, K=n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=vector(K, k, Col(serlaplace(log(serconvol(q, p^k))))));
  Mat(vector(K, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*W[i])/k!));
}
my(T=M(7)); for(n=1, #T, print(T[n, 1..n]))

T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*A322279(n,j).

A002032 Number of n-colored connected graphs on n labeled nodes.

Original entry on oeis.org

1, 1, 2, 24, 912, 87360, 19226880, 9405930240, 10142439229440, 24057598104207360, 125180857812868300800, 1422700916050060841779200, 35136968950395142864227532800, 1876028272361273394915958613606400, 215474119792145796020405035320528076800

Offset: 0

N. J. A. Sloane

nonn

Every connected graph on n nodes can be colored with n colors in exactly n! ways, so this sequence is just n! * A001187(n). - Andrew Howroyd, Dec 03 2018

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50
R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Cf. A002027. A002028, A002029, A002030, A002031.

Cf. A001187, A322278, A322279, A322280.

(* b = A001187 *) b[n_] := b[n] = If[n == 0, 1, 2^(n(n-1)/2) - Sum[k* Binomial[n, k]*2^((n-k)(n-k-1)/2)*b[k], {k, 1, n-1}]/n];
a[n_] := n! b[n];
Array[a, 14] (* Jean-François Alcover, Aug 16 2019, using Alois P. Heinz's code for A001187 *)

seq(n) = {Vec(serlaplace(serlaplace(1 + log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n))))))} \\ Andrew Howroyd, Dec 03 2018

a(n) = n!*A001187(n). - Andrew Howroyd, Dec 03 2018
Define M_0(k)=1, M_n(0)=0, M_n(k) = Sum_{r=0..n} C(n,r)*2^(r*(n-r))*M_r(k-1) [M_n(k) = A322280(n,k)], m_n(k) = M_n(k) -Sum_{r=1..n-1} C(n-1,r-1)*m_r(k)*M_{n-r}(k) [m_n(k) = A322279(n,k)], f_n(k) = Sum_{r=1..k} (-1)^(k-r)*C(k,r)*m_n(r). This sequence gives a(n) = f_n(n). - Sean A. Irvine, May 29 2013, edited Andrew Howroyd, Dec 03 2018
The above formula is referenced by sequences A002027-A002030, A002031. - Andrew Howroyd, Dec 03 2018

More terms from Sean A. Irvine, May 29 2013
Name clarified by Andrew Howroyd, Dec 03 2018
a(0)=1 prepended by Andrew Howroyd, Jan 05 2024

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

Original entry on oeis.org

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

A372920 Total number of n-colorings of all graphs on n labeled nodes.

Original entry on oeis.org

1, 1, 6, 123, 7108, 1058885, 386056326, 332908216711, 662759754883080, 2991536714452469769, 30189087071961437767690, 673536638307789642838763531, 32919693104791033024939149066252, 3498056629389633452501822564131061773, 802931613320922331646386276441560583143438

Offset: 0

Alois P. Heinz, May 16 2024

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..76

Main diagonal of A322280.

Cf. A000035, A006125.

nmax = 76;
a[n_] := 2^(n(n-1)/2)*n!*SeriesCoefficient[Sum[x^i/(2^(i(i-1)/2)*i!), {i, 0, nmax}]^n, {x, 0, n}];
Table[a[n],{n,0,nmax}] (* Jean-François Alcover, May 28 2024 *)

a(n) = A322280(n,n).

a(n) == n (mod 2) for n >= 1.

A337161 Square array read by antidiagonals: T(n,k) is the number of simple labeled graphs G with vertex set V(G) = {v_1,...,v_n} along with a (coloring) function C:V(G) ->[k] such that v_i adjacent to v_j implies C(v_i) != C(v_j) and i=0, k>=0.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 9, 10, 1, 0, 1, 5, 16, 35, 34, 1, 0, 1, 6, 25, 84, 195, 162, 1, 0, 1, 7, 36, 165, 644, 1635, 1090, 1, 0, 1, 8, 49, 286, 1605, 7620, 21187, 10370, 1, 0, 1, 9, 64, 455, 3366, 24389, 143748, 430467, 139522, 1, 0, 1, 10, 81, 680, 6279, 62310, 599685, 4412164, 13812483, 2654722, 1, 0, 1, 11, 100, 969, 10760, 136871, 1882054, 24413445, 223233540, 702219779, 71435266, 1, 0

Offset: 0

Geoffrey Critzer, Jan 28 2021

			  1, 1,    1,     1,      1,      1,       1, ...
  0, 1,    2,     3,      4,      5,       6, ...
  0, 1,    4,     9,     16,     25,      36, ...
  0, 1,   10,    35,     84,    165,     286, ...
  0, 1,   34,   195,    644,   1605,    3366, ...
  0, 1,  162,  1635,   7620,  24389,   62310, ...
  0, 1, 1090, 21187, 143748, 599685, 1882054, ...

R. P. Stanley, Enumerative Combinatorics, Vol I, Second Edition, Section 3.18.

Cf. A322280, A117402 (column k=2).

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

Let e(x) = Sum_{n>=0} x^n/2^binomial(n,2). Then e(x)^k = Sum_{n>=0} Z_n(k)*x^n/2^biomial(n,2) and T(n,k) = Z_n(k). Z_n(k) is the zeta polynomial of the class of posets described in A117402.

cp's OEIS Frontend

A047863 Number of labeled graphs with 2-colored nodes where black nodes are only connected to white nodes and vice versa.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

PARI

Python

SageMath

Formula

Extensions

A191371 Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A334282 Number of properly colored labeled graphs on n nodes so that the color function is surjective onto {c_1,c_2,...,c_k} for some k, 1<=k<=n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A223887 Number of 4-colored labeled graphs on n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A002032 Number of n-colored connected graphs on n labeled nodes.