A058872 -id:A058872 - cp's OEIS frontend

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

1, 3, 13, 81, 721, 9153, 165313, 4244481, 154732801, 8005686273, 587435092993, 61116916981761, 9011561121239041, 1882834327457349633, 557257804202631217153, 233610656002563147038721, 138681207656726645785559041

Offset: 1

N. J. A. Sloane

a(n) = A058872(n) + 1. This sequence counts the empty graph on n nodes which is not allowed in A058872. - Geoffrey Critzer, Oct 07 2012

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

Vincenzo Librandi, Table of n, a(n) for n = 1..100 (first 32 terms from R. W. Robinson)
S. R. Finch, Bipartite, k-colorable and k-colored graphs (2*A000684)
S. R. Finch, Bipartite, k-colorable and k-colored graphs, June 5, 2003. [Cached copy, with permission of the author]
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19.
D. A. Klarner, The number of graded partially ordered sets, J. Combin. Theory, 6 (1969), 12-19. [Annotated scanned copy]
A. Nymeyer and R. W. Robinson, Tabulation of the Numbers of Labeled Bipartite Blocks and Related Classes of Bicolored Graphs, 1982 [Annotated scanned copy of unpublished MS and letter from R.W.R.]
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976

2 * A000683(n) + 1.

Cf. A058872, A111636, A134531.

With[{nn=20},Rest[CoefficientList[Series[Sum[x^n/(1-2^n x)^n,{n,nn}],{x,0,nn}], x]]] (* Harvey P. Dale, Nov 24 2011 *)

a(n)=polcoeff(sum(k=1,n,x^k/(1-2^k*x +x*O(x^n))^k),n) \\ Paul D. Hanna, Sep 14 2009

G.f.: A(x) = Sum_{n>=1} x^n/(1 - 2^n*x)^n. - Paul D. Hanna, Sep 14 2009
G.f.: 1/(W(0)-x) where W(k) = x*(x*2^k-1)^k - (x*2^(k+1)-1)^(k+1) + x*((2*x*2^k-1)^(2*k+2))/W(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 17 2012
From Peter Bala, Apr 01 2013: (Start)
a(n) = Sum_{k = 0..n-1} binomial(n-1,k)*2^(k*(n-k)).
a(n) = Sum_{k = 0..n} 2^k*A111636(n,k).
Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence (but with an offset of 0) is E(x)*E(2*x) = Sum_{n >= 0} a(n+1)*x^n/(n!*2^C(n,2)) = 1 + 3*x + 13*x^2/(2!*2) + 81*x^3/(3!*2^3) + 721*x^4/(4!*2^6) + .... Cf. A134531. (End)

a(15) onwards added by N. J. A. Sloane, Oct 19 2006 from the Robinson reference

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

Original entry on oeis.org

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)

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

A201143 Irregular triangular array read by rows T(n,k) is the number of 2-colored labeled graphs that have exactly k edges, n >= 2, 0 <= k <= A033638(n).

Original entry on oeis.org

1, 1, 3, 6, 3, 7, 24, 30, 16, 3, 15, 80, 180, 220, 155, 60, 10, 31, 240, 840, 1740, 2340, 2106, 1260, 480, 105, 10, 63, 672, 3360, 10360, 21840, 33054, 36757, 30240, 18270, 7910, 2331, 420, 35, 127, 1792, 12096, 51520, 154280, 343392, 586488, 782944, 824670, 686840, 450296, 229656, 89208, 25480, 5040, 616, 35

Offset: 2

Geoffrey Critzer, Nov 27 2011

In each such graph: (i) no two nodes of the same color are adjacent, (ii) the colors are interchangeable, and (iii) there must be at least one vertex of each color.

			Triangle begins:
   1,   1;
   3,   6,   3;
   7,  24,  30,   16,    3;
  15,  80, 180,  220,  155,   60,   10;
  31, 240, 840, 1740, 2340, 2106, 1260, 480, 105, 10;

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

Andrew Howroyd, Table of n, a(n) for n = 2..1403 (rows 2..25)

Row sums are A058872.

Row lengths appear to be A033638(n).

Flatten[CoefficientList[Expand[Table[Sum[Binomial[n, k] (1 + x)^(k (n - k)), {k, 1, n - 1}]/2!, {n, 1,7}]], x]]

Row(n) = {Vecrev(sum(k=1, n-1, binomial(n,k)*(1+x)^(k*(n-k))/2))}
{ for(n=2, 8, print(Row(n))) } \\ Andrew Howroyd, Apr 18 2021

O.g.f. of row n: Sum_{k=0..n-1} binomial(n,k)*(1+x)^(k*(n-k))/2.

Terms a(42) and beyond from Andrew Howroyd, Apr 18 2021

cp's OEIS Frontend

A000684 Number of colored labeled n-node graphs with 2 interchangeable colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

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

A201143 Irregular triangular array read by rows T(n,k) is the number of 2-colored labeled graphs that have exactly k edges, n >= 2, 0 <= k <= A033638(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions