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!)
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 * A130559 A135256 A090586

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 10 12:30 EST 2019. Contains 329895 sequences. (Running on oeis4.)