login
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

%I #25 May 13 2022 10:43:21

%S 1,2,3,3,10,16,4,21,104,218,5,36,328,3044,9608,6,55,752,14814,291968,

%T 1540944,7,78,1440,45960,2183400,96928992,882033440,8,105,2456,111010,

%U 9133760,1098209328,112282908928,1793359192848

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

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

%F A(1,k) = k.

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

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

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

%F A(n,4) = A353996(n+1). - _Brendan McKay_, May 13 2022

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

%e First six rows and columns:

%e 1 2 3 4 5 6

%e 3 10 21 36 55 78

%e 16 104 328 752 1440 2456

%e 218 3044 14814 45960 111010 228588

%e 9608 291968 2183400 9133760 27755016 68869824

%e 1540944 96928992 1098209328 6154473664 23441457680 69924880288

%e ...

%e n=4, k=3 with A329546:

%e A(4,3) = 3*218 + 3*2608 + 6336 = 14814.

%o (PARI) \\ here C(p) computes A328773 sequence value for given partition.

%o 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}

%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i], v[j]))) + sum(i=1, #v, v[i]-1)}

%o 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, [])}

%o \\ here mulp(v) computes the multiplicity of the given partition. (see A072811)

%o 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!}

%o wC(p)=mulp(p)*C(p)

%o A329546(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}

%o Row(n)=vector(6, k, binomial(k)[2..min(k,n)+1]*A329546(n)[1..min(k,n)]~)

%o { for(n=0, 6, print(Row(n))) }

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

%K nonn,tabl

%O 1,2

%A _Peter Dolland_, Nov 23 2019