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

A000683 Number of colorings of labeled graphs on n nodes using exactly 2 colors, divided by 4.

Original entry on oeis.org

0, 1, 6, 40, 360, 4576, 82656, 2122240, 77366400, 4002843136, 293717546496, 30558458490880, 4505780560619520, 941417163728674816, 278628902101315608576, 116805328001281573519360, 69340603828363322892779520, 58287619305053298399714082816, 69366390252412220606233109200896

Offset: 1

N. J. A. Sloane

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. A213441 counts those colorings of labeled graphs on n vertices that use exactly two colors. This sequence is 1/4 of A213441 (1/4 of column 2 of Table 1 in Read). - Peter Bala, Apr 11 2013

A047863 counts colorings of labeled graphs on n vertices that use two or fewer colors. - Peter Bala, Apr 11 2013

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

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

a(n)=(A047863(n)-2)/4.
A diagonal of A058843.
One quarter of A213441.

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, 2]/2; Table[a[n], {n, 1, maxn}] (* Jean-François Alcover, Sep 21 2011 *)

Reference gives generating function.

a(n) ~ c * 2^(n^2/4+n-3/2)/sqrt(Pi*n), where c = Sum_{k = -infinity..infinity} 2^(-k^2) = 2.128936827211877... if n is even and c = Sum_{k = -infinity..infinity} 2^(-(k+1/2)^2) = 2.12893125051302... if n is odd. - Vaclav Kotesovec, Jun 24 2013

More terms from Vladeta Jovovic, Feb 02 2000

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

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

A058872 Number of 2-colored labeled graphs with n nodes.

Original entry on oeis.org

0, 2, 12, 80, 720, 9152, 165312, 4244480, 154732800, 8005686272, 587435092992, 61116916981760, 9011561121239040, 1882834327457349632, 557257804202631217152, 233610656002563147038720, 138681207656726645785559040, 116575238610106596799428165632

Offset: 1

N. J. A. Sloane, Jan 07 2001

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. A213441 counts those colorings of labeled graphs on n vertices that use exactly two colors. This sequence is 1/2 of A213441 (1/2 of column 2 of Table 1 in Read). - Peter Bala, Apr 11 2013

A047863 counts colorings of labeled graphs on n vertices that use two or fewer colors. - Peter Bala, Apr 11 2013

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 18, Table 1.5.1.
A. Mukhopadhyay, Lupanov decoding networks, in A. Mukhopadhyay, ed., Recent Developments in Switching Theory, Ac. Press, 1971, Chap. 3, see esp. p. 82 (number of shell functions).

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

A diagonal of A058843.

One half of A213441.

A058872 := n->add(binomial(n,k)*2^(n-k)*2^(k*(n-k)),k=0..n-1);

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

A241669 Irregular triangular array read by rows: T(n,k) is the number of 2-colored simple labeled graphs on n nodes that have exactly k edges, 0<=k<=A002620(n), n>=1.

Original entry on oeis.org

0, 2, 2, 6, 12, 6, 14, 48, 60, 32, 6, 30, 160, 360, 440, 310, 120, 20, 62, 480, 1680, 3480, 4680, 4212, 2520, 960, 210, 20, 126, 1344, 6720, 20720, 43680, 66108, 73514, 60480, 36540, 15820, 4662, 840, 70, 254, 3584, 24192, 103040, 308560, 686784, 1172976, 1565888, 1649340, 1373680, 900592, 459312, 178416, 50960, 10080, 1232, 70, 510, 9216, 80640, 451584, 1808352, 5491584, 13102992, 25128720, 39312018, 50638224, 53981928, 47698560, 34869744, 20975472, 10281672, 4044096, 1246644, 290304, 48048, 5040, 252

Offset: 1

Geoffrey Critzer, Aug 08 2014

			Triangle begins:
  0,
  2,  2,
  6,  12,  6,
  14, 48,  60,   32,   6,
  30, 160, 360,  440,  310,  120,  20,
  62, 480, 1680, 3480, 4680, 4212, 2520, 960, 210, 20

R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.

Cf. A002620, A213441 (row sums).

nn=10;f[x_]:=Sum[x^n/(n!*(1+y)^(n^2/2)),{n,0,nn}];CoefficientList[Table[n!*(1+y)^(n^2/2),{n,0,nn}]CoefficientList[Series[(f[x]-1)^2,{x,0,nn}],x]//Simplify//Expand,y]//Grid

E.g.f.: Sum_{n>=1} (exp(1 + y)^n*x - 1)*x^n/n!.

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

A000683 Number of colorings of labeled graphs on n nodes using exactly 2 colors, divided by 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

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

A058872 Number of 2-colored labeled graphs with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

A241669 Irregular triangular array read by rows: T(n,k) is the number of 2-colored simple labeled graphs on n nodes that have exactly k edges, 0<=k<=A002620(n), n>=1.

Views

Author

Keywords

Examples