|
%I #21 Dec 03 2019 03:59:55
%S 1,3,4,16,72,64,218,2608,6336,4096,9608,272752,1336320,2113536,
%T 1048576,1540944,93847104,812045184,2337046528,2689597440,1073741824,
%U 882033440,110518842048,1580861402112,7344135176192,14676310097920,13200581984256,4398046511104
%N Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors arbitrarily assigned (1 <= k <= n).
%C The values are weighted subtotals of the rows of the irregular triangle A328773.
%C The weight of a color scheme is the multiplicity A072811(n,k) with k as the index of the induced partition.
%C T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
%C If we do not consider the exchange of colors with different sizes to be different digraphs, we can impose an order on the colors, which leads to A329541.
%F T(n,1) = A000273(n) = A328773(n,1).
%F T(n,n) = A053763(n) = A328773(n,A000041(n)).
%F T(n,n-1) = (n-1)*A328773(n,A000041(n)-1).
%F T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition with k elements} A072811(n,i)*A328773(n,i).
%e First six rows:
%e 1
%e 3 4
%e 16 72 64
%e 218 2608 6336 4096
%e 9608 272752 1336320 2113536 1048576
%e 1540944 93847104 812045184 2337046528 2689597440 1073741824
%e n=4, k=2: Partitions: [3,1] and [2,2] with indices 2 and 3 and multiplicities 2 and 1: T(4,2) = Sum_{i=2,3} A072811(4,i)*A328773(4,i) = 2*752 + 1104 = 2608.
%e n=6, k=3: Partitions: [4,1,1], [3,2,1], [2,2,2] with indexes 4, 6, 8 and multiplicities 3, 6, 1: T(6,3) = Sum_{i=4,6,8} A072811(6,i)*A328773(6,i) = 3*45277312 + 6*90196736 + 1*135032832 = 812045184.
%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 Row(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
%o { for(n=0, 10, print(Row(n))) }
%Y Cf. A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme).
%Y Cf. A072811 (multiplicity of color schemes).
%Y Cf. A329541 (ordered colors).
%Y Cf. A309980 (reflexive/anti-reflexive: just two colors).
%K nonn,tabl
%O 1,2
%A _Peter Dolland_, Nov 16 2019
|
