|
%I #30 Apr 14 2019 13:10:39
%S 1,1,1,1,6,1,1,40,24,1,1,360,640,80,1,1,4576,24000,7040,240,1,1,82656,
%T 1367296,878080,62720,672,1,1,2122240,122056704,169967616,23224320,
%U 487424,1792,1,1,77366400,17282252800,53247344640,13440516096
%N Triangle T(n,k) = C_n(k)/2^(k*(k-1)/2) where C_n(k) = number of k-colored labeled graphs with n nodes (n >= 1, 1 <= k <= n).
%C From _Peter Bala_, Apr 12 2013: (Start)
%C A coloring of a simple graph G is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color.
%C Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2*2!) + x^3/(2^3*3!) + .... Read has shown that (E(x) - 1)^k is a generating function for labeled graphs on n nodes that can be colored using exactly k colors. Cases include A213441 (k = 2), A213442 (k = 3) and A224068 (k = 4).
%C If colorings of a graph using k colors are counted as the same if they differ only by a permutation of the colors then a generating function is 1/k!*(E(x) - 1)^k , which is a generating function for the k-th column of A058843. Removing a further factor of 2^C(k,2) gives 1/(k!*2^C(k,2))*(E(x) - 1)^k as a generating function for the k-th column of this triangle. (End)
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.
%H Andrew Howroyd, <a href="/A058875/b058875.txt">Table of n, a(n) for n = 1..1275</a>
%H S. R. Finch, <a href="http://www.people.fas.harvard.edu/~sfinch/">Bipartite, k-colorable and k-colored graphs</a>
%H S. R. Finch, <a href="/A191371/a191371.pdf">Bipartite, k-colorable and k-colored graphs</a>, June 5, 2003. [Cached copy, with permission of the author]
%H R. C. Read, <a href="http://cms.math.ca/10.4153/CJM-1960-035-0">The number of k-colored graphs on labelled nodes</a>, Canad. J. Math., 12 (1960), 410-414.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/k-ColorableGraph.html">k-Colorable Graph</a>
%F C_n(k) = Sum_{i=1..n-1} binomial(n, i)*2^(i*(n-i))*C_i(k-1)/k.
%F From _Peter Bala_, Apr 12 2013: (Start)
%F Recurrence equation: T(n,k) = 1/2^(k-1)*Sum_{i = 1..n-1} binomial(n-1,i)*2^(i*(n-i))*T(i,k-1).
%F Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + .... Then a generating function for this triangle is E(x*(E(z) - 1)) = 1 + x*z + (x + x^2 )*z^2/(2!*2) + (x + 6*x^2 + x^3)*z^3/(3!*2^3) + (x + 40*x^2 + 24*x^3 + x^4)*z^4/(4!*2^6) + .... Cf. A008277 with e.g.f. exp(x*(exp(z) - 1)).
%F The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x*sum {k = 0..n-1} binomial(n-1,k)*2^(k*(n-k))*R(k,x/2) with R(0,x) = 1. The row polynomials appear to have only real zeros.
%F Column 2 = 1/(2!*2)*A213441; column 3 = 1/(3!*2^3)*A213442; column 4 = 1/(4!*2^6)*A224068. (End)
%F T(n,k) = A058843(n,k)/2^binomial(k,2). - _Andrew Howroyd_, Nov 30 2018
%e Triangle begins:
%e 1;
%e 1, 1;
%e 1, 6, 1;
%e 1, 40, 24, 1;
%e 1, 360, 640, 80, 1;
%e 1, 4576, 24000, 7040, 240, 1;
%e 1, 82656, 1367296, 878080, 62720, 672, 1;
%e ...
%t maxn=8; t[_,1]=1; t[n_,k_]:=t[n,k]=Sum[Binomial[n,j]*2^(j*(n-j))*t[j,k-1]/k,{j,1,n-1}]; Flatten[Table[t[n,k]/2^Binomial[k,2], {n,1,maxn},{k,1,n}]] (* _Geoffrey Critzer_, Oct 06 2012, after code from _Jean-François Alcover_ in A058843 *)
%o (PARI)
%o b(n)={n!*2^binomial(n,2)}
%o T(n,k)={b(n)*polcoef((sum(j=1, n, x^j/b(j)) + O(x*x^n))^k, n)/b(k)} \\ _Andrew Howroyd_, Nov 30 2018
%Y Apart from scaling, same as A058843.
%Y Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202, also A006218.
%Y Cf. A213441, A213442, A224068.
%K nonn,easy,tabl
%O 1,5
%A _N. J. A. Sloane_, Jan 07 2001
|
