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
Examples
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.
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
- 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
Programs
-
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}] -
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 -
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
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) + ....
Comments