cp's OEIS Frontend

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

%I A329874 #25 May 13 2022 10:43:21
%S A329874 1,2,3,3,10,16,4,21,104,218,5,36,328,3044,9608,6,55,752,14814,291968,
%T A329874 1540944,7,78,1440,45960,2183400,96928992,882033440,8,105,2456,111010,
%U A329874 9133760,1098209328,112282908928,1793359192848
%N 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).
%C A329874 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 A329874 A(1,k) = k.
%F A329874 A(2,k) = k*(2*k+1).
%F A329874 A(n,1) = A000273(n).
%F A329874 A(n,2) = A000595(n).
%F A329874 A(n,4) = A353996(n+1). - _Brendan McKay_, May 13 2022
%F A329874 A(n,k) = Sum_{i=1..min(n,k)} binomial(k,i)*A329546(n,i).
%e A329874 First six rows and columns:
%e A329874       1        2          3          4           5           6
%e A329874       3       10         21         36          55          78
%e A329874      16      104        328        752        1440        2456
%e A329874     218     3044      14814      45960      111010      228588
%e A329874    9608   291968    2183400    9133760    27755016    68869824
%e A329874 1540944 96928992 1098209328 6154473664 23441457680 69924880288
%e A329874 ...
%e A329874 n=4, k=3 with A329546:
%e A329874 A(4,3) = 3*218 + 3*2608 + 6336 = 14814.
%o A329874 (PARI) \\ here C(p) computes A328773 sequence value for given partition.
%o A329874 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 A329874 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 A329874 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 A329874 \\ here mulp(v) computes the multiplicity of the given partition. (see A072811)
%o A329874 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 A329874 wC(p)=mulp(p)*C(p)
%o A329874 A329546(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
%o A329874 Row(n)=vector(6, k, binomial(k)[2..min(k,n)+1]*A329546(n)[1..min(k,n)]~)
%o A329874 { for(n=0, 6, print(Row(n))) }
%Y A329874 Cf. A000273 digraphs with one color, A000595 binary relations, A329546 digraphs with exactly k colors, A328773 digraphs with a given color scheme.
%K A329874 nonn,tabl
%O A329874 1,2
%A A329874 _Peter Dolland_, Nov 23 2019