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.

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,8

Comments

Not all colors need to be used.

Links

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.

Formula

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

Example

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

Mathematica

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

Prog

(PARI)
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, ]))

Crossrefs

Columns k=2..4 are A047863, A191371, A223887.

Cf. A058843, A058875, A322278, A322279.

Sequence in context: A183135 A294042 A287316 * A331436 A343097 A343095

Adjacent sequences: A322277 A322278 A322279 * A322281 A322282 A322283

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 01 2018

Status

approved