A191371 -id:A191371 - cp's OEIS frontend

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

Original entry on oeis.org

1, 2, 8, 64, 1023, 32596, 2062592, 257798069, 63135260853, 29939766625614, 27055039857514327

Offset: 1

Eric W. Weisstein, May 25 2003

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]
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, A084279, A084281, A084282.

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

A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.

Original entry on oeis.org

1, 5, 41, 545, 11681, 402305, 22207361, 1961396225, 276825510401, 62368881977345, 22413909724518401, 12840603873823473665, 11720394922432296755201, 17037597932370037286600705

Offset: 1

N. J. A. Sloane

Sequence represents 1/3 of the number of 3-colored labeled graphs on n nodes. Indeed, on p. 413 of the Read paper, column 3 is 3, 15, 123, 1635, ...; or see A047863. - Emeric Deutsch, May 06 2004

R. C. Read, personal communication.
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).

T. D. Noe, Table of n, a(n) for n = 1..50
S. R. Finch, Bipartite, k-colorable and k-colored graphs (3*A000685)
S. 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. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
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

Cf. A000683, A047863, A191371, A223887.

c[0]:=1: for n from 1 to 30 do c[n]:=sum(binomial(n,i)*2^(i*(n-i)),i=0..n) od: a:=n->(1/3)*sum(binomial(n,j)*2^(j*(n-j))*c[j],j=0..n): seq(a(n),n=1..19);

a[n_] := 1/3*Sum[ 2^((i-j)*j + i*(n-i))*Binomial[n, i]*Binomial[i, j], {i, 0, n}, {j, 0, i}]; Table[ a[n], {n, 1, 14}] (* Jean-François Alcover, Dec 07 2011, after Emeric Deutsch *)

a(n) = (1/3)Sum_{j=0..n} binomial(n, j)*2^(j(n-j))*c(j) where c(n) = Sum_{i=0..n} binomial(n, i)*2^(i(n-i)) = A047863(n). - Emeric Deutsch, May 06 2004
From Peter Bala, Apr 12 2013: (Start)
a(n) = 1/3*A191371(n). Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/3*E(x)^3 - 1/3 = Sum_{n >= 1} a(n)*x^n/(n!*2^C(n,2)) = x + 5*x^2/(2!*2) + 41*x^3/(3!*2^3) + .... In general, E(x)^k, k = 1, 2, ..., is a generating function for labeled k-colored graphs (see Read). For examples see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)

More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004

A000686 Number of 4-colored labeled graphs on n nodes, divided by 4.

Original entry on oeis.org

1, 7, 85, 1777, 63601, 3882817, 403308865, 71139019777, 21276992674561, 10778161937857537, 9238819435213784065, 13390649605615389843457, 32796747486424209782108161, 135669064080920007649863745537, 947468281528010179181982467702785, 11166618111585805201637975219611631617

Offset: 1

N. J. A. Sloane

Sequence represents 1/4 of the number of 4-colored labeled graphs on n nodes. Indeed, on p. 413 of the Read paper, column 4 is 4, 28, 340, 7108, ... - Emeric Deutsch, May 06 2004

R. C. Read, personal communication.
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).

S. R. Finch, Bipartite, k-colorable and k-colored graphs. (4*{a(n)})
S. 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. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976.

Cf. A000683, A000685, A223887.

b[n_] := Sum[ 2^((i-j)*j + i*(n-i))*Binomial[n, i]*Binomial[i, j], {i, 0, n}, {j, 0, i}]; a[n_] := 1/4*Sum[ Binomial[n, k]*2^(k*(n-k))*b[k], {k, 0, n}]; Table[a[n], {n, 1, 14}] (* Jean-François Alcover, Dec 07 2011, after Emeric Deutsch *)

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

a(n) = (1/4)*Sum_{k=0..n} binomial(n, k)*2^(k(n-k))*b(k), where b(0)=1 and b(k) = 3*A000685(k) for k > 0. - Emeric Deutsch, May 06 2004
From Peter Bala, Apr 12 2013: (Start)
a(n) = (1/4)*A223887(n).
a(n) = (1/4)*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 (1/4)*(E(x)^4 - 1) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = x + 7*x^2/(2!*2) + 85*x^3/(3!*2^3) + .... (End)

More terms from Pab Ter (pabrlos(AT)yahoo.com) and Emeric Deutsch, May 05 2004

A002028 Number of connected graphs on n labeled nodes, each node being colored with one of 3 colors, such that no edge joins nodes of the same color.

Original entry on oeis.org

1, 3, 6, 42, 618, 15990, 668526, 43558242, 4373213298, 677307561630, 162826875512646, 61183069270120842, 36134310487980825258, 33673533885068169649830, 49646105434209446798290206, 116002075479856331220877149042, 430053223599741677879550609246498, 2531493110297317758855120762121050990

Offset: 0

N. J. A. Sloane

nonn

R. C. Read, personal communication.
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.

Column k=3 of A322279.

Cf. A002031, A002032.

f[{k_, r_, m_}]:= Binomial[m+r+k, k] Binomial[m+r, r] 2^(k r +k m + r m);
  a = Sum[Total[Map[f, Compositions[n, 3]]] x^n/n!, {n, 0, 20}];
  Range[0, 20]! CoefficientList[Series[Log[a]+1, {x, 0, 20}], x] (* Geoffrey Critzer, Jun 02 2011 *)

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

E.g.f.: log(A(x))+1 where A(x) is the e.g.f. for A191371. - Geoffrey Critzer, Jun 02 2011
a(n) = m_n(3) using the functions defined in A002032. - Sean A. Irvine, May 29 2013
Logarithmic transform of A191371. - Andrew Howroyd, Dec 03 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A000685 Number of 3-colored labeled graphs on n nodes, divided by 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000686 Number of 4-colored labeled graphs on n nodes, divided by 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A002028 Number of connected graphs on n labeled nodes, each node being colored with one of 3 colors, such that no edge joins nodes of the same color.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula