A213442 -id:A213442 - 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)

A191371 Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color.

Original entry on oeis.org

1, 3, 15, 123, 1635, 35043, 1206915, 66622083, 5884188675, 830476531203, 187106645932035, 67241729173555203, 38521811621470420995, 35161184767296890265603, 51112793797110111859802115, 118291368253025368001553530883, 435713124846749574718274002747395, 2553666761436949125065383836043837443

Offset: 0

Geoffrey Critzer, Jun 01 2011

Cf. A213442, which counts colorings of labeled graphs on n vertices using exactly 3 colors. For 3-colorable labeled graphs on n vertices see A076315. - Peter Bala, Apr 12 2013

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

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

Andrew Howroyd, Table of n, a(n) for n = 0..50
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=3 of A322280.

Cf. A047863. A000685, A076315, A223887.

f[{k_,r_,m_}]:= Binomial[m+r+k,k] Binomial[m+r,r] 2^ (k r + k m + r m); Table[Total[Map[f,Compositions[n,3]]],{n,0,20}]

seq(n)={my(p=(sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))^3); Vecrev(sum(j=0, n, j!*2^binomial(j,2)*polcoef(p,j)*x^j))} \\ Andrew Howroyd, Dec 03 2018

from sympy import binomial
def a047863(n): return sum([binomial(n, k)*2**(k*(n - k)) for k in range(n + 1)])
def a(n): return sum([binomial(n, k)*2**(k*(n - k))*a047863(k) for k in range(n + 1)]) # Indranil Ghosh, Jun 03 2017

a(n) = Sum(C(n,k)*C(n-k,r)*2^(k*r+k*m+r*m)) where the sum is taken over all nonnegative solutions to k + r + m = n.
From Peter Bala, Apr 12 2013: (Start)
a(n) = Sum_{k = 0..n} binomial(n,k)*2^(k*(n-k))*A047863(k).
a(n) = 3*A000685(n) for n >= 1.
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is E(x)^3 = sum {n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 15*x^2/(2!*2) + 123*x^3/(3!*2^3) + 1635*x^4/(4!*2^6) + ....
In general, for k = 1, 2, ..., E(x)^k is a generating function for labeled k-colored graphs (see Read). For other examples see A047863 (k = 2) and A223887 (k = 4). (End)

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

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

A224068 Number of labeled graphs on n vertices that can be colored using exactly 4 colors.

Original entry on oeis.org

0, 0, 0, 1536, 122880, 10813440, 1348730880, 261070258176, 81787921367040, 42364317235937280, 36686317873382031360, 53408511909378681470976, 131046345314766385022238720, 542471805171085602081503969280, 3789399960645715708906355231293440

Offset: 1

Peter Bala, Apr 10 2013

A223887 counts labeled 4-colored graphs on n vertices, that is, colorings of labeled graphs on n vertices using 4 or fewer colors.

This sequence differs in that it counts only those colorings of labeled graphs on n vertices that use exactly 4 colors. Cf. A213441 and A213442.

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. A213441, A213442, A223887.

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

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

a(n) = Sum_{k=2..n-2} C(n,k)*2^(k*(n-k))*A213441(k)*A213441(n-k).

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)^4 = 1536*x^4/(4!*2^6) + 122880*x^5/(5!*2^10) + 10813440*x^6/(6!*2^15) + ... + a(n)*x^n/(n!*2^(n*(n-1)/2)) + ... (see Read).

A006201 Number of colorings of labeled graphs on n nodes using exactly 3 colors, divided by 48.

Original entry on oeis.org

0, 0, 1, 24, 640, 24000, 1367296, 122056704, 17282252800, 3897054412800, 1400795928395776, 802530102499344384, 732523556206878392320, 1064849635418836398243840, 2464403435614136308036796416

Offset: 1

N. J. A. Sloane

Equals 1/48*A213442. - Peter Bala, Apr 12 2013

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, table 1.5.1, column 3 (divided by 8).
R. C. Read, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (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. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

Cf. A000683. A diagonal of A058843. A213442.

F2[n_] := Sum[Binomial[n, r]*2^(r*(n-r)), {r, 1, n-1}]; F3[n_] := Sum[Binomial[n, r]*2^(r*(n-r))*F2[r], {r, 1, n-1}]; a[n_] := F3[n]/48; Table[a[n], {n, 1, 15}] (* Jean-François Alcover, Mar 06 2014, after Maple code in A213442 *)

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)/48, -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 1/48*(E(x) - 1)^3 = x^3/(3!*2^3) + 24*x^4/(4!*2^6) + 640*x^6/(5!*2^10) + ... (see Read). - Peter Bala, Apr 12 2013

More terms from Vladeta Jovovic, Feb 03 2000

A058873 Number of 3-colored labeled graphs with n nodes.

Original entry on oeis.org

0, 0, 8, 192, 5120, 192000, 10938368, 976453632, 138258022400, 31176435302400, 11206367427166208, 6420240819994755072, 5860188449655027138560, 8518797083350691185950720, 19715227484913090464294371328, 72618853907514273117149186752512

Offset: 1

N. J. A. Sloane, Jan 07 2001

nonn

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. A213442 counts those colorings of labeled graphs on n vertices that use exactly three colors. In this sequence, graph colorings that differ only by a permutation of the three colors are considered to be the same. Hence a(n) = 1/3!*A213442(n). [Peter Bala, Apr 12 2013]

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

Robert Israel, Table of n, a(n) for n = 1..97
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

A diagonal of A058843. A213442.

E:= Sum(x^n/(n!*2^(n*(n-1)/2)),n=1..infinity):
G:= 1/6*E^3:
S:= series(G,x,21):
seq(coeff(S,x,n)*n!*2^(n*(n-1)/2),n=1..20); # Robert Israel, Aug 01 2018

f[list_] := (Apply[Multinomial, list] * 2^((Total[list]^2-Total[Table[list[[i]]^2, {i, 1, Length[list]}]])/2))/3!; Table[Total[Map[f, Select[Compositions[n, 3], Count[#, 0]==0&]]], {n, 1, 20}] (* Geoffrey Critzer, Oct 24 2011 *)

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

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 1/6*(E(x) - 1)^3 = 8*x^3/(3!*2^3) + 192*x^4/(4!*2^6) + 5120*x^5/(5!*2^10) + ... (see Read). - Peter Bala, Apr 13 2013

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

A191371 Number of simple labeled graphs with (at most) 3-colored nodes such that no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

A224068 Number of labeled graphs on n vertices that can be colored using exactly 4 colors.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A006201 Number of colorings of labeled graphs on n nodes using exactly 3 colors, divided by 48.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions