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
Examples
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 ... ...
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.
Crossrefs
Programs
-
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 *) -
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,]))
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).
Comments