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

A322280 Array read by antidiagonals: T(n,k) is the number of graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 6, 1, 0, 1, 4, 15, 26, 1, 0, 1, 5, 28, 123, 162, 1, 0, 1, 6, 45, 340, 1635, 1442, 1, 0, 1, 7, 66, 725, 7108, 35043, 18306, 1, 0, 1, 8, 91, 1326, 20805, 254404, 1206915, 330626, 1, 0, 1, 9, 120, 2191, 48486, 1058885, 15531268, 66622083, 8488962, 1, 0

Offset: 0

Andrew Howroyd, Dec 01 2018

Not all colors need to be used.

			Array begins:
===============================================================
n\k| 0 1      2        3          4           5           6
---+-----------------------------------------------------------
0  | 1 1      1        1          1           1           1 ...
1  | 0 1      2        3          4           5           6 ...
2  | 0 1      6       15         28          45          66 ...
3  | 0 1     26      123        340         725        1326 ...
4  | 0 1    162     1635       7108       20805       48486 ...
5  | 0 1   1442    35043     254404     1058885     3216486 ...
6  | 0 1  18306  1206915   15531268    95261445   386056326 ...
7  | 0 1 330626 66622083 1613235460 15110296325 83645197446 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. C. Read, The number of k-colored graphs on labelled nodes, Canad. J. Math., 12 (1960), 410-414.
R. C. Read and E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Columns k=0..4 are A000007, A000012, A047863, A191371, A223887.
Main diagonal gives A372920.
Cf. A058843, A058875, A322278, A322279.

nmax = 10;
T[n_, k_] := n!*2^Binomial[n, 2]*SeriesCoefficient[Sum[ x^i/(i!* 2^Binomial[i, 2]), {i, 0, nmax}]^k, {x, 0, n}];
Table[T[n - k, k], {n, 0, nmax}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Sep 23 2019 *)

M(n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*j!*2^binomial(j, 2)) + O(x*x^n));
  matconcat([1, Mat(vector(n, k, Col(serconvol(q, p^k))))]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

T(n,k) = n!*2^binomial(n,2) * [x^n](Sum_{i>=0} x^i/(i!*2^binomial(i,2)))^k.

T(n,k) = Sum_{j=0..k} binomial(k,j)*j!*A058843(n,j).

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 6, 6, 0, 0, 1, 5, 12, 42, 38, 0, 0, 1, 6, 20, 132, 618, 390, 0, 0, 1, 7, 30, 300, 3156, 15990, 6062, 0, 0, 1, 8, 42, 570, 9980, 136980, 668526, 134526, 0, 0, 1, 9, 56, 966, 24330, 616260, 10015092, 43558242, 4172198, 0, 0

Offset: 0

Andrew Howroyd, Dec 01 2018

Not all colors need to be used.

			Array begins:
===============================================================
n\k| 0 1      2        3          4           5           6
---+-----------------------------------------------------------
0  | 1 1      1        1          1           1           1 ...
1  | 0 1      2        3          4           5           6 ...
2  | 0 0      2        6         12          20          30 ...
3  | 0 0      6       42        132         300         570 ...
4  | 0 0     38      618       3156        9980       24330 ...
5  | 0 0    390    15990     136980      616260     1956810 ...
6  | 0 0   6062   668526   10015092    65814020   277164210 ...
7  | 0 0 134526 43558242 1199364852 11878194300 67774951650 ...
...

Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. C. Read, E. M. Wright, Colored graphs: A correction and extension, Canad. J. Math. 22 1970 594-596.

Columns k=2..5 are A002027, A002028, A002029, A002030.

Cf. A058843, A058875, A322278, A322280.

M(n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=Mat(vector(n, k, Col(serlaplace(1 + log(serconvol(q, p^k)))))));
  matconcat([1, W]);
}
my(T=M(7)); for(n=1, #T, print(T[n,]))

k-th column is the logarithmic transform of the k-th column of A322280.

E.g.f of k-th column: 1 + log(Sum_{n>=0} A322280(n,k)*x^n/n!).

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

1, 0, 1, 0, 3, 4, 0, 19, 84, 38, 0, 195, 2470, 3140, 728, 0, 3031, 108390, 307390, 186360, 26704, 0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256, 0, 2086099, 726782784, 9030799218, 20784069600, 14401134944, 3463311488, 251548592

Offset: 1

Andrew Howroyd, Dec 01 2018

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with k parts. See A322064 for the definition of stable partition.

			Triangle begins:
  1;
  0,     1;
  0,     3,       4;
  0,    19,      84,       38;
  0,   195,    2470,     3140,      728;
  0,  3031,  108390,   307390,   186360,    26704;
  0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A322064.
Columns k=2..4 are A001832(for n > 1), A322330, A322331.
Right diagonal is A001187.
Cf. A058843, A058875, A322279, A322280.

M(n, K=n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=vector(K, k, Col(serlaplace(log(serconvol(q, p^k))))));
  Mat(vector(K, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*W[i])/k!));
}
my(T=M(7)); for(n=1, #T, print(T[n, 1..n]))

T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*A322279(n,j).

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

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

A322280 Array read by antidiagonals: T(n,k) is the number of graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322279 Array read by antidiagonals: T(n,k) is the number of connected graphs on n labeled nodes, each node being colored with one of k colors, where no edge connects two nodes of the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

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