A224068 -id:A224068 - cp's OEIS frontend

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

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

Offset: 1

N. J. A. Sloane, Jan 07 2001

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)

			Triangle begins:
  1;
  1,    2;
  1,   12,      8;
  1,   80,    192,     64;
  1,  720,   5120,   5120,   1024;
  1, 9152, 192000, 450560, 245760, 32768;
  ...

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

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.

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.

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:

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

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

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)

A223887 Number of 4-colored labeled graphs on n vertices.

Original entry on oeis.org

1, 4, 28, 340, 7108, 254404, 15531268, 1613235460, 284556079108, 85107970698244, 43112647751430148, 36955277740855136260, 53562598422461559373828, 131186989945696839128432644, 542676256323680030599454982148

Offset: 0

Peter Bala, Apr 10 2013

A simple graph G is a k-colorable graph if it is possible to assign one of k' <= k colors to each vertex of G so that no two adjacent vertices receive the same color. Such an assignment of colors is called a coloring function for the graph.
A k-colored graph is a k-colorable graph together with its coloring function. This sequence gives the number of labeled 4-colored graphs on n vertices. An example is given below.
See A047863 for labeled 2-colored graphs on n vertices and A191371 for labeled 3-colored graphs on n vertices. See A076316 for labeled 4-colorable graphs on n vertices and A224068 for the count of labeled graphs colored using exactly 4 colors.

			a(2) = 28: There are two labeled 4-colorable graphs on 2 nodes, namely
A)  1    2  B)  1    2
    o    o      o----o
Using 4 colors there are 16 ways to color the graph of type A and 4*3 = 12 ways to color the graph of type B so that adjacent vertices do not share the same color. Thus there are in total 28 labeled 4-colored graphs on 2 vertices.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, 1973.

Andrew Howroyd, Table of n, a(n) for n = 0..50
Steven R. Finch, Bipartite, k-colorable and k-colored graphs
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

Column k=4 of A322280.

Equals 4 * A000686, A047863 (labeled 2-colored graphs), A076316, A191371 (labeled 3-colored graphs), A224068.

N=66;  x='x+O('x^N);
E=sum(n=0, N, x^n/(n!*2^binomial(n,2)) );
tgf=E^4;  v=concat(Vec(tgf));
v=vector(#v, n, v[n] * (n-1)! * 2^((n-1)*(n-2)/2) )
/* Joerg Arndt, Apr 10 2013 */

a(n) = sum {k = 0..n} binomial(n,k)*2^(k*(n-k))*b(k)*b(n-k), where b(n) := sum {k = 0..n} binomial(n,k)*2^(k*(n-k)).

Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^4 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 4*x + 28*x^2/(2!*2) + 340*x^3/(3!*2^3) + .... In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Stanley).

A213442 Number of 3-colored graphs on n labeled nodes.

Original entry on oeis.org

0, 0, 48, 1152, 30720, 1152000, 65630208, 5858721792, 829548134400, 187058611814400, 67238204562997248, 38521444919968530432, 35161130697930162831360, 51112782500104147115704320, 118291364909478542785766227968, 435713123445085638702895120515072, 2553666760604861879125023961330483200

Offset: 1

N. J. A. Sloane, Jun 12 2012

A191371 counts labeled 3-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 3 or fewer colors. This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly three colors. Cf. A213441 and A224068. - Peter Bala, Apr 10 2013

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Alois P. Heinz, Table of n, a(n) for n = 1..75
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
Wikipedia, Graph coloring

Cf. A191371, A213441, A224068.

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
F3:=n->add(binomial(n,r)*2^(r*(n-r))*F2(r),r=1..n-1);
[seq(F3(n),n=1..20)];

Table[Sum[Binomial[n,r]*2^(r*(n-r))*Sum[Binomial[r,s]*2^(s*(r-s)),{s,1,r-1}],{r,1,n-1}],{n,1,20}] (* Vaclav Kotesovec, Jul 23 2013 *)

seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^3), -n)} \\ Andrew Howroyd, Nov 30 2018

Let E(x) = sum {n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function is (E(x) - 1)^3 = 48*x^3/(3!*2^3) + 1152*x^4/(4!*2^6) + 30720*x^5/(5!*2^10) + ... (see Read). - Peter Bala, Apr 10 2013

a(n) = O(2^(n^2/3)*3^n/n). - Vaclav Kotesovec, Jul 23 2013

A213441 Number of 2-colored graphs on n labeled nodes.

Original entry on oeis.org

0, 4, 24, 160, 1440, 18304, 330624, 8488960, 309465600, 16011372544, 1174870185984, 122233833963520, 18023122242478080, 3765668654914699264, 1114515608405262434304, 467221312005126294077440, 277362415313453291571118080, 233150477220213193598856331264, 277465561009648882424932436803584, 467466753447825987214906927108587520

Offset: 1

N. J. A. Sloane, Jun 11 2012

From Peter Bala, Apr 10 2013: (Start)
A coloring of a simple graph is a choice of color for each graph vertex such that no two vertices sharing the same edge have the same color. This sequence counts only those colorings of labeled graphs on n vertices that use exactly two colors.
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 Read has shown that (E(x) - 1)^k is a generating function for counting labeled graphs colored using precisely k colors. This is the case k = 2. For other cases see A213442 (k = 3) and A224068 (k = 4).
A coloring of a graph G that uses k or fewer colors is called a k-coloring of G. The graph G is k-colored if a k-coloring of G exists.
Then E(x)^k is a generating function for the enumeration of labeled k-colored graphs on n vertices (see Stanley). For cases see A047863 (k = 2), A191371 (k = 3) and A223887 (k = 4). (End)

			a(2) = 4: Denote the vertex coloring by o and *. The 4 labeled graphs on 2 vertices that can be colored using exactly two colors are
....1....2............1....2
....o....*............*----o
...........................
....1....2............1....2
....*....o............o----*
- _Peter Bala_, Apr 10 2013

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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. Volume 306, Issues 10-11, 28 May 2006, Pages 905-909.
Eric Weisstein's World of Mathematics, k-Colorable Graph
Wikipedia, Graph coloring

Cf. A047863, A058843, A191371, A213442, A223887, A224068.

F2:=n->add(binomial(n,r)*2^(r*(n-r)), r=1..n-1);
[seq(F2(n),n=1..20)];

nn=20;a[x_]:=Sum[x^n/(n!*(2^(n^2/2))),{n,0,nn}];Drop[Table[n!*(2^(n^2/2)),{n,0,nn}]CoefficientList[Series[(a[x]-1)^2,{x,0,nn}],x],1] (* Geoffrey Critzer, Aug 05 2014 *)

a(n) = sum(k=1,n-1, binomial(n,k)*2^(k*(n-k)) ); /* Joerg Arndt, Apr 10 2013 */

From Peter Bala, Apr 10 2013: (Start)
a(n) = Sum_{k = 1..n-1} binomial(n,k)*2^(k*(n-k)). a(n) = A047863(n) - 2.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)) = 1 + x + x^2/(2!*2) + x^3/(3!*2^3) + x^4/(4!*2^6) + .... Then a generating function is (E(x) - 1)^2 = 4*x^2/(2!*2) + 24*x^3/(3!*2^3) + 160*x^4/(4!*2^6) + ....
Sequence is 1/2*(column 2) from A058843. (End)
E.g.f.: Sum_{n>=1}(exp(2^n*x)-1)*x^n/n!. - Geoffrey Critzer, Aug 11 2014

A006202 Number of colorings of labeled graphs on n nodes using exactly 4 colors, divided by 4!*2^6.

Original entry on oeis.org

0, 0, 0, 1, 80, 7040, 878080, 169967616, 53247344640, 27580935700480, 23884321532149760, 34771166607668412416, 85316631064301031915520, 353171748158258855521812480, 2467057266045387831319241687040, 29078599995993904385498084987109376

Offset: 1

N. J. A. Sloane

Equals 1/1536*A224068. - Peter Bala, Apr 12 2013

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, col. 4 of Table 1.5.1 (divided by 64).
R. C. Read, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..80
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

A diagonal of A058875.

Cf. A000683, A224068.

maxn = 16;
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}];
a[n_] := t[n, 4]/64;
Array[a, maxn]

seq(n)={Vec(serconvol(sum(j=1, n, x^j*j!*2^binomial(j,2)) + O(x*x^n), (sum(j=1, n, x^j/(j!*2^binomial(j,2))) + O(x*x^n))^4)/1536, -n)} \\ Andrew Howroyd, Nov 30 2018

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

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jan 07 2001

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)

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

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

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Steven R. Finch, Bipartite, k-colorable and k-colored graphs
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.
Eric Weisstein's World of Mathematics, k-Colorable Graph

Apart from scaling, same as A058843.
Columns give A058872 and A000683, A058873 and A006201, A058874 and A006202, also A006218.
Cf. A213441, A213442, A224068.

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A223887 Number of 4-colored labeled graphs on n vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A213442 Number of 3-colored graphs on n labeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A213441 Number of 2-colored graphs on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A006202 Number of colorings of labeled graphs on n nodes using exactly 4 colors, divided by 4!*2^6.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula