A191371 -id:A191371 - 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

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Original entry on oeis.org

1, 3, 13, 81, 721, 9153, 165313, 4244481, 154732801, 8005686273, 587435092993, 61116916981761, 9011561121239041, 1882834327457349633, 557257804202631217153, 233610656002563147038721, 138681207656726645785559041

Offset: 1

N. J. A. Sloane

a(n) = A058872(n) + 1. This sequence counts the empty graph on n nodes which is not allowed in A058872. - Geoffrey Critzer, Oct 07 2012

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

Vincenzo Librandi, Table of n, a(n) for n = 1..100 (first 32 terms from R. W. Robinson)
S. R. Finch, Bipartite, k-colorable and k-colored graphs (2*A000684)
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

With[{nn=20},Rest[CoefficientList[Series[Sum[x^n/(1-2^n x)^n,{n,nn}],{x,0,nn}], x]]] (* Harvey P. Dale, Nov 24 2011 *)

a(n)=polcoeff(sum(k=1,n,x^k/(1-2^k*x +x*O(x^n))^k),n) \\ Paul D. Hanna, Sep 14 2009

G.f.: A(x) = Sum_{n>=1} x^n/(1 - 2^n*x)^n. - Paul D. Hanna, Sep 14 2009
G.f.: 1/(W(0)-x) where W(k) = x*(x*2^k-1)^k - (x*2^(k+1)-1)^(k+1) + x*((2*x*2^k-1)^(2*k+2))/W(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012
From Peter Bala, Apr 01 2013: (Start)
a(n) = Sum_{k = 0..n-1} binomial(n-1,k)*2^(k*(n-k)).
a(n) = Sum_{k = 0..n} 2^k*A111636(n,k).
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with an offset of 0) is E(x)*E(2*x) = Sum_{n >= 0} a(n+1)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 13*x^2/(2!*2) + 81*x^3/(3!*2^3) + 721*x^4/(4!*2^6) + .... Cf. A134531. (End)

a(15) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

A047864 Number of labeled bipartite graphs with n nodes.

Original entry on oeis.org

1, 1, 2, 7, 41, 376, 5177, 103237, 2922446, 116011231, 6433447397, 498234407452, 54007795331921, 8213123246906761, 1756336596363006842, 528975889250504033527, 224688018516023267969441, 134708289561117007261966816

Offset: 0

N. J. A. Sloane

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 406.
H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 80, Eq. 3.11.5.

T. D. Noe, Table of n, a(n) for n = 0..50
Vladislav Bína and Jiří Přibil, Note on enumeration of labeled split graphs, Comment. Math. Univ. Carolin. 56,2 (2015) 133-137.
S. R. Finch, Bipartite, k-colorable and k-colored graphs. [Broken link]
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 32.
Eric Weisstein's World of Mathematics, n-Colorable Graph.
H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 89, Eq. 3.11.5.

Row sums of A117279.
The unlabeled version is A033995.
Cf. A001832, A047863.

nn = 20; a = Sum[Sum[Binomial[n, k] 2^(k (n - k)), {k, 0, n}] x^n/n!, {n, 0, nn}]; Range[0, nn]! CoefficientList[Series[a^(1/2), {x, 0, nn}], x]  (* Geoffrey Critzer, Jan 15 2012 *)

N=18; x='x+O('x^N); Vec(serlaplace(sqrt(sum(n=0, N, exp(2^n*x)*x^n/n!)))) \\ Gheorghe Coserea, Nov 13 2017

E.g.f.: sqrt( e.g.f. for A047863 ).

A322280 Array read by antidiagonals: T(n,k) is the number of 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, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 26, 1, 0, 1, 5, 28, 123, 162, 1, 0, 1, 6, 45, 340, 1635, 1442, 1, 0, 1, 7, 66, 725, 7108, 35043, 18306, 1, 0, 1, 8, 91, 1326, 20805, 254404, 1206915, 330626, 1, 0, 1, 9, 120, 2191, 48486, 1058885, 15531268, 66622083, 8488962, 1, 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 1      6       15         28          45          66 ...
3  | 0 1     26      123        340         725        1326 ...
4  | 0 1    162     1635       7108       20805       48486 ...
5  | 0 1   1442    35043     254404     1058885     3216486 ...
6  | 0 1  18306  1206915   15531268    95261445   386056326 ...
7  | 0 1 330626 66622083 1613235460 15110296325 83645197446 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. C. Read and E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Columns k=0..4 are A000007, A000012, A047863, A191371, A223887.
Main diagonal gives A372920.
Cf. A058843, A058875, A322278, A322279.

nmax = 10;
T[n_, k_] := n!*2^Binomial[n, 2]*SeriesCoefficient[Sum[ x^i/(i!* 2^Binomial[i, 2]), {i, 0, nmax}]^k, {x, 0, n}];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 23 2019 *)

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*j!*2^binomial(j, 2)) + O(x*x^n));
  matconcat([1, Mat(vector(n, k, Col(serconvol(q, p^k))))]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

T(n,k) = n!*2^binomial(n,2) * [x^n](Sum_{i>=0} x^i/(i!*2^binomial(i,2)))^k.

T(n,k) = Sum_{j=0..k} binomial(k,j)*j!*A058843(n,j).

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

A213442 Number of 3-colored graphs on n labeled nodes.

Original entry on oeis.org

0, 0, 48, 1152, 30720, 1152000, 65630208, 5858721792, 829548134400, 187058611814400, 67238204562997248, 38521444919968530432, 35161130697930162831360, 51112782500104147115704320, 118291364909478542785766227968, 435713123445085638702895120515072, 2553666760604861879125023961330483200

Offset: 1

N. J. A. Sloane, Jun 12 2012

A191371 counts labeled 3-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 3 or fewer colors. This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly three colors. Cf. A213441 and A224068. - Peter Bala, Apr 10 2013

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..75
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
Wikipedia, Graph coloring

Cf. A191371, A213441, A224068.

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
F3:=n->add(binomial(n,r)*2^(r*(n-r))*F2(r),r=1..n-1);
[seq(F3(n),n=1..20)];

Table[Sum[Binomial[n,r]*2^(r*(n-r))*Sum[Binomial[r,s]*2^(s*(r-s)),{s,1,r-1}],{r,1,n-1}],{n,1,20}] (* Vaclav Kotesovec, Jul 23 2013 *)

seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^3), -n)} \\ Andrew Howroyd, Nov 30 2018

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 is (E(x) - 1)^3 = 48*x^3/(3!*2^3) + 1152*x^4/(4!*2^6) + 30720*x^5/(5!*2^10) + ... (see Read). - Peter Bala, Apr 10 2013

a(n) = O(2^(n^2/3)*3^n/n). - Vaclav Kotesovec, Jul 23 2013

A111636 Triangle read by rows: T(n,k) (0<=k<=n) is the number of labeled graphs having k blue nodes and n-k green ones and only nodes of different colors can be joined by an edge.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 12, 12, 1, 1, 32, 96, 32, 1, 1, 80, 640, 640, 80, 1, 1, 192, 3840, 10240, 3840, 192, 1, 1, 448, 21504, 143360, 143360, 21504, 448, 1, 1, 1024, 114688, 1835008, 4587520, 1835008, 114688, 1024, 1, 1, 2304, 589824, 22020096, 132120576, 132120576, 22020096, 589824, 2304, 1

Offset: 0

Emeric Deutsch, Aug 09 2005

Row sums yield A047863. T(2*n,n) = A111637(n). T(n,1) = A001787(n).

			T(2,1)=4 because we have B G, B--G, G B and G--B, where B (G) stands for a blue (green) node and -- denotes an edge.
Triangle starts:
  1;
  1,  1;
  1,  4,  1;
  1, 12, 12,  1;
  1, 32, 96, 32, 1;
  ...

H. S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, p. 88, Eq. 3.11.2.

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]
W. Wang and T. Wang, Generalized Riordan array, Discrete Mathematics, Vol. 308, No. 24, 6466-6500.

Cf. A047863, A111637, A001787.
Cf. A134530 (matrix log), A134531.
Cf. A000684, A011266, A038845, A140802, A224069 (matrix inverse).

T:=(n,k)->binomial(n,k)*2^(k*(n-k)): for n from 0 to 9 do seq(T(n,k),k=0..n) od; # yields sequence in triangular form

nn=6;f[x_,y_]:=Sum[Exp[x 2^n](y x)^n/n!,{n,0,nn}];Range[0,nn]!CoefficientList[Series[f[x,y],{x,0,nn}],{x,y}]//Grid (* Geoffrey Critzer, Sep 07 2013 *)

T(n, k)=2^[k(n-k)]*C(n, k).
Matrix log yields triangle A134530, where A134530(n,k) = A134531(n-k)*(2^k)^(n-k)*C(n,k). - Paul D. Hanna, Nov 11 2007
From Peter Bala, Aug 13 2012: (Start)
Let f(n) = n!*2^binomial(n,2) = A011266(n). Then T(n,k) = f(n)/(f(k)*f(n-k)).
E.g.f.: Sum_{n >= 0} exp(2^n*t*x)*x^n/n! = 1 + (1+t)*x + (1+4*t+t^2)*x^2/2! + ....
O.g.f.: Sum_{n >= 0} x^n/(1-2^n*t*x)^(n+1) = 1 + (1+t)*x + (1+4*t+t^2)*x^2 + .... O.g.f. for column k: 1/(1-2^k*x)^(k+1).
Recurrence equation: T(n,k) = 2^k*T(n-1,k) + 2^(n-k)*T(n-1,k-1).
Column k = 2: A038845. Column k = 3: A140802. Sum_{k = 0..n} k*T(n,k) = n*A000684(n). (End)
From Peter Bala, Apr 09 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 for this sequence is E(z)*E(x*z) = 1 + (1 + x)*z + (1 + 4*x + x^2)*z^2/(2!*2) + (1 + 12*x + 12*x^2 + x^3)*z^3/(3!*2^3) + .... Cf. Pascal's triangle A007318 with an e.g.f. of exp(z)*exp(x*z).
This is a generalized Riordan array (E(x), x) with respect to the sequence n!*2^C(n,2), as defined by Wang and Wang.
The n-th power of this triangle has a generating function E(z)^n*E(x*z). See A224069 for the inverse array (n = -1).
The n-th row is a log-concave sequence and hence unimodal.
The row polynomials satisfy the recurrence equation R(n+1,x) = 2^n*x*R(n,x/2) + R(n,2*x) with R(0,x) = 1, as well as R'(n,2*x) = n*2^(n-1)*R(n-1,x) (the ' denotes differentiation w.r.t. x). The row polynomials appear to have only real zeros.
Sum_{k = 0..n} (-1)^k*T(2*n+1,k) = 0;
Sum_{k = 0..n} (-1)^k*2^k*T(2*n,k) = 0;
Sum_{k = 0..n} 2^k*T(n,k) = A000684(n). (End)
T(n,k+1) = Product_{i=0..k} (T(n-i,1)/T(i+1,1)) for 0 <= k < n. - Werner Schulte, Nov 13 2018

A213441 Number of 2-colored graphs on n labeled nodes.

Original entry on oeis.org

0, 4, 24, 160, 1440, 18304, 330624, 8488960, 309465600, 16011372544, 1174870185984, 122233833963520, 18023122242478080, 3765668654914699264, 1114515608405262434304, 467221312005126294077440, 277362415313453291571118080, 233150477220213193598856331264, 277465561009648882424932436803584, 467466753447825987214906927108587520

Offset: 1

N. J. A. Sloane, Jun 11 2012

From Peter Bala, Apr 10 2013: (Start)
A coloring of a simple graph is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color. This sequence counts only those colorings of labeled graphs on n vertices that use exactly two colors.
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 Read has shown that (E(x) - 1)^k is a generating function for counting labeled graphs colored using precisely k colors. This is the case k = 2. For other cases see A213442 (k = 3) and A224068 (k = 4).
A coloring of a graph G that uses k or fewer colors is called a k-coloring of G. The graph G is k-colored if a k-coloring of G exists.
Then E(x)^k is a generating function for the enumeration of labeled k-colored graphs on n vertices (see Stanley). For cases see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)

			a(2) = 4: Denote the vertex coloring by o and *. The 4 labeled graphs on 2 vertices that can be colored using exactly two colors are
....1....2............1....2
....o....*............*----o
...........................
....1....2............1....2
....*....o............o----*
- _Peter Bala_, Apr 10 2013

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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. Volume 306, Issues 10-11, 28 May 2006, Pages 905-909.
Eric Weisstein's World of Mathematics, k-Colorable Graph
Wikipedia, Graph coloring

Cf. A047863, A058843, A191371, A213442, A223887, A224068.

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
[seq(F2(n),n=1..20)];

nn=20;a[x_]:=Sum[x^n/(n!*(2^(n^2/2))),{n,0,nn}];Drop[Table[n!*(2^(n^2/2)),{n,0,nn}]CoefficientList[Series[(a[x]-1)^2,{x,0,nn}],x],1] (* Geoffrey Critzer, Aug 05 2014 *)

a(n) = sum(k=1,n-1, binomial(n,k)*2^(k*(n-k)) ); /* Joerg Arndt, Apr 10 2013 */

From Peter Bala, Apr 10 2013: (Start)
a(n) = Sum_{k = 1..n-1} binomial(n,k)*2^(k*(n-k)). a(n) = A047863(n) - 2.
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 is (E(x) - 1)^2 = 4*x^2/(2!*2) + 24*x^3/(3!*2^3) + 160*x^4/(4!*2^6) + ....
Sequence is 1/2*(column 2) from A058843. (End)
E.g.f.: Sum_{n>=1}(exp(2^n*x)-1)*x^n/n!. - Geoffrey Critzer, Aug 11 2014

A058875 Triangle T(n,k) = C_n(k)/2^(k*(k-1)/2) where C_n(k) = number of k-colored labeled graphs with n nodes (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 6, 1, 1, 40, 24, 1, 1, 360, 640, 80, 1, 1, 4576, 24000, 7040, 240, 1, 1, 82656, 1367296, 878080, 62720, 672, 1, 1, 2122240, 122056704, 169967616, 23224320, 487424, 1792, 1, 1, 77366400, 17282252800, 53247344640, 13440516096

Offset: 1

N. J. A. Sloane, Jan 07 2001

From Peter Bala, Apr 12 2013: (Start)
A coloring of a simple graph G is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2*2!) + x^3/(2^3*3!) + .... Read has shown that (E(x) - 1)^k is a generating function for labeled graphs on n nodes that can be colored using exactly k colors. Cases include A213441 (k = 2), A213442 (k = 3) and A224068 (k = 4).
If colorings of a graph using k colors are counted as the same if they differ only by a permutation of the colors then a generating function is 1/k!*(E(x) - 1)^k , which is a generating function for the k-th column of A058843. Removing a further factor of 2^C(k,2) gives 1/(k!*2^C(k,2))*(E(x) - 1)^k as a generating function for the k-th column of this triangle. (End)

			Triangle begins:
  1;
  1,     1;
  1,     6,       1;
  1,    40,      24,      1;
  1,   360,     640,     80,     1;
  1,  4576,   24000,   7040,   240,   1;
  1, 82656, 1367296, 878080, 62720, 672, 1;
  ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.

Andrew Howroyd, Table of n, a(n) for n = 1..1275
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.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Apart from scaling, same as A058843.
Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202, also A006218.
Cf. A213441, A213442, A224068.

maxn=8; t[,1]=1; t[n,k_]:=t[n,k]=Sum[Binomial[n,j]*2^(j*(n-j))*t[j,k-1]/k,{j,1,n-1}]; Flatten[Table[t[n,k]/2^Binomial[k,2], {n,1,maxn},{k,1,n}]]  (* Geoffrey Critzer, Oct 06 2012, after code from Jean-François Alcover in A058843 *)

b(n)={n!*2^binomial(n,2)}
T(n,k)={b(n)*polcoef((sum(j=1, n, x^j/b(j)) + O(x*x^n))^k, n)/b(k)} \\ Andrew Howroyd, Nov 30 2018

C_n(k) = Sum_{i=1..n-1} binomial(n, i)*2^(i*(n-i))*C_i(k-1)/k.
From Peter Bala, Apr 12 2013: (Start)
Recurrence equation: T(n,k) = 1/2^(k-1)*Sum_{i = 1..n-1} binomial(n-1,i)*2^(i*(n-i))*T(i,k-1).
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 for this triangle is E(x*(E(z) - 1)) = 1 + x*z + (x + x^2 )*z^2/(2!*2) + (x + 6*x^2 + x^3)*z^3/(3!*2^3) + (x + 40*x^2 + 24*x^3 + x^4)*z^4/(4!*2^6) + .... Cf. A008277 with e.g.f. exp(x*(exp(z) - 1)).
The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x*sum {k = 0..n-1} binomial(n-1,k)*2^(k*(n-k))*R(k,x/2) with R(0,x) = 1. The row polynomials appear to have only real zeros.
Column 2 = 1/(2!*2)*A213441; column 3 = 1/(3!*2^3)*A213442; column 4 = 1/(4!*2^6)*A224068. (End)
T(n,k) = A058843(n,k)/2^binomial(k,2). - Andrew Howroyd, Nov 30 2018

A084279 Number of labeled 3-colorable (i.e., chromatic number <= 3) graphs on n nodes.

Original entry on oeis.org

1, 2, 8, 63, 958, 27554, 1457047, 137144754, 22249524024, 6032417530135, 2663111111716110, 1876540387225350958

Offset: 1

Eric W. Weisstein, May 25 2003

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]
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 8c665c7
Eric Weisstein's World of Mathematics, n-Colorable Graph

Cf. A047864, A084280, A084281, A084282.

a(7)-a(12) added using tinygraph by Falk Hüffner, Jun 20 2018

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

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A047864 Number of labeled bipartite graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322280 Array read by antidiagonals: T(n,k) is the number of 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

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A213442 Number of 3-colored graphs on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI