The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A058843 Triangle T(n,k) = C_n(k) where C_n(k) = number of k-colored labeled graphs with n nodes (n >= 1, 1<=k<=n). 14
 1, 1, 2, 1, 12, 8, 1, 80, 192, 64, 1, 720, 5120, 5120, 1024, 1, 9152, 192000, 450560, 245760, 32768, 1, 165312, 10938368, 56197120, 64225280, 22020096, 2097152, 1, 4244480, 976453632, 10877927424, 23781703680, 15971909632, 3758096384 (list; table; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 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). In this triangle, colorings of a labeled graph using k colors that differ only by a permutation of the k colors are treated as the same giving 1/k!*(E(x) - 1)^k as a generating function function for the k-th column. (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 R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414. 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) = sum {i = 1..n-1} binomial(n-1,i)*2^(i*(n-i))*T(i,k-1). A generating function: exp(x*(E(z) - 1)) = 1 + x*z + (x + 2*x^2)*z^2/(2!*2) + (x + 12*x^2 + 8*x^3)*z^3/(3!*2^3) + .... Cf. A008277 with e.g.f. exp(x*(exp(z) - 1)). A generating function for column k: 1/k!*(E(x) - 1)^k = sum {n>=k} T(n,k)x^n/(n!*2^C(n,2)). The row polynomials R(n,x) satisfy the recurrence equation R(n,x) = x*(1 + sum {k = 0..n-1} binomial(n-1,k)*2^(k*(n-k))*R(k,x)) with R(1,x) = x. The row polynomials appear to have only real zeros. Column 2 = 1/2!*A213441; Column 3 = 1/3!*A213442; Column 4 = 1/4!*A224068. (End) EXAMPLE Triangle begins: 1; 1, 2; 1, 12, 8; 1, 80, 192, 64; 1, 720, 5120, 5120, 1024; 1, 9152, 192000, 450560, 245760, 32768; ... MAPLE for p from 1 to 20 do C[p, 1] := 1; od: for k from 2 to 20 do for p from 1 to k-1 do C[p, k] := 0; od: od: for k from 2 to 10 do for p from k to 10 do C[p, k] := add( binomial(p, n)*2^(n*(p-n))*C[n, k-1]/k, n=1..p-1); od: od: 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], {n, 1, maxn}, {k, 1, n}]] (* Jean-François Alcover, Sep 21 2011 *) PROG (PARI) T(n, k)={n!*2^binomial(n, 2)*polcoef((sum(j=1, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))^k, n)/k!} \\ Andrew Howroyd, Nov 30 2018 CROSSREFS Apart from scaling, same as A058875. Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202, also A006218. A213441, A213442, A224068. Row sums give A240936. Sequence in context: A085752 A074966 A128413 * A343861 A130559 A135256 Adjacent sequences: A058840 A058841 A058842 * A058844 A058845 A058846 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 29 20:40 EST 2023. Contains 367447 sequences. (Running on oeis4.)