A000685 -id:A000685 - cp's OEIS frontend

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

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)

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

cp's OEIS Frontend

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