login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A191371 Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color. 15
1, 3, 15, 123, 1635, 35043, 1206915, 66622083, 5884188675, 830476531203, 187106645932035, 67241729173555203, 38521811621470420995, 35161184767296890265603, 51112793797110111859802115, 118291368253025368001553530883, 435713124846749574718274002747395, 2553666761436949125065383836043837443 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

REFERENCES

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..50

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

FORMULA

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)

EXAMPLE

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.

MATHEMATICA

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}]

PROG

(Python)

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

(PARI) 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

CROSSREFS

Column k=3 of A322280.

Cf. A047863. A000685, A076315, A223887.

Sequence in context: A160884 A173468 A197505 * A113077 A251661 A230657

Adjacent sequences:  A191368 A191369 A191370 * A191372 A191373 A191374

KEYWORD

nonn,easy

AUTHOR

Geoffrey Critzer, Jun 01 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 22:16 EST 2020. Contains 331166 sequences. (Running on oeis4.)