login
This site is supported by donations to The OEIS Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A058875 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). 6
1, 1, 1, 1, 6, 1, 1, 40, 24, 1, 1, 360, 640, 80, 1, 1, 4576, 24000, 7040, 240, 1, 1, 82656, 1367296, 878080, 62720, 672, 1, 1, 2122240, 122056704, 169967616, 23224320, 487424, 1792, 1, 1, 77366400, 17282252800, 53247344640, 13440516096 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

From Peter Bala, Apr 12 2013: (Start)

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.

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

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)

REFERENCES

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

S. R. Finch, Bipartite, k-colorable and k-colored graphs

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.

Eric Weisstein's World of Mathematics, k-Colorable Graph

FORMULA

C_n(k) = Sum_{i=1..n-1} binomial(n, i)*2^(i*(n-i))*C_i(k-1)/k.

From Peter Bala, Apr 12 2013: (Start)

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

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

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.

Column 2 = 1/(2!*2)*A213441; column 3 = 1/(3!*2^3)*A213442; column 4 = 1/(4!*2^6)*A224068. (End)

T(n,k) = A058843(n,k)/2^binomial(k,2). - Andrew Howroyd, Nov 30 2018

EXAMPLE

Triangle begins:

  1;

  1,     1;

  1,     6,       1;

  1,    40,      24,      1;

  1,   360,     640,     80,     1;

  1,  4576,   24000,   7040,   240,   1;

  1, 82656, 1367296, 878080, 62720, 672, 1;

  ...

MATHEMATICA

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 *)

PROG

(PARI)

b(n)={n!*2^binomial(n, 2)}

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

CROSSREFS

Apart from scaling, same as A058843.

Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202, also A006218.

Cf. A213441, A213442, A224068.

Sequence in context: A203338 A158116 A172343 * A156764 A156765 A015117

Adjacent sequences:  A058872 A058873 A058874 * A058876 A058877 A058878

KEYWORD

nonn,easy,tabl

AUTHOR

N. J. A. Sloane, Jan 07 2001

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 December 14 17:41 EST 2019. Contains 329979 sequences. (Running on oeis4.)