login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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
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.
Sequence in context: A173468 A197505 A348903 * A113077 A251661 A230657
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 11:59 EDT 2024. Contains 371254 sequences. (Running on oeis4.)