A329874 Array read by antidiagonals: A(n,k) = number of digraphs on n unlabeled nodes, arbitrarily colored with k given colors (n >= 1, k >= 1).

1, 2, 3, 3, 10, 16, 4, 21, 104, 218, 5, 36, 328, 3044, 9608, 6, 55, 752, 14814, 291968, 1540944, 7, 78, 1440, 45960, 2183400, 96928992, 882033440, 8, 105, 2456, 111010, 9133760, 1098209328, 112282908928, 1793359192848

Offset

1,2

Comments

The coloring of nodes is unrestricted. There is no constraint that all of the k colors have to be used. Nodes with different colors are counted as distinct, nodes with the same color are not. For digraphs with a fixed color set see A329546.

Links

Table of n, a(n) for n=1..36.

Formula

A(1,k) = k.

A(2,k) = k*(2*k+1).

A(n,1) = A000273(n).

A(n,2) = A000595(n).

A(n,4) = A353996(n+1). - Brendan McKay, May 13 2022

A(n,k) = Sum_{i=1..min(n,k)} binomial(k,i)*A329546(n,i).

Example

First six rows and columns:
      1        2          3          4           5           6
      3       10         21         36          55          78
     16      104        328        752        1440        2456
    218     3044      14814      45960      111010      228588
   9608   291968    2183400    9133760    27755016    68869824
1540944 96928992 1098209328 6154473664 23441457680 69924880288
...
n=4, k=3 with A329546:
A(4,3) = 3*218 + 3*2608 + 6336 = 14814.

Prog

(PARI) \\ here C(p) computes A328773 sequence value for given partition.
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}
C(p)={((i, v)->if(i>#p, 2^edges(v), my(s=0); forpart(q=p[i], s+=permcount(q)*self()(i+1, concat(v, Vec(q)))); s/p[i]!))(1, [])}
\\ here mulp(v) computes the multiplicity of the given partition. (see A072811)
mulp(v) = {my(p=(#v)!, k=1); for(i=2, #v, k=if(v[i]==v[i-1], k+1, p/=k!; 1)); p/k!}
wC(p)=mulp(p)*C(p)
A329546(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n), #p==m], , 4))) | m<-[1..n]]}
Row(n)=vector(6, k, binomial(k)[2..min(k, n)+1]*A329546(n)[1..min(k, n)]~)
{ for(n=0, 6, print(Row(n))) }

Crossrefs

Cf. A000273 digraphs with one color, A000595 binary relations, A329546 digraphs with exactly k colors, A328773 digraphs with a given color scheme.

Sequence in context: A100652 A094416 A218868 * A152300 A117030 A155758

Adjacent sequences: A329871 A329872 A329873 * A329875 A329876 A329877

Keyword

nonn,tabl

Author

Peter Dolland, Nov 23 2019

Status

approved