|
%I #22 Sep 24 2023 11:10:57
%S 1,3,4,16,36,64,218,1856,2112,4096,9608,136376,445440,528384,1048576,
%T 1540944,62020640,270506880,449511424,537919488,1073741824,882033440,
%U 55259421024,435010671104,1101584588800,1834672455680,2200096997376,4398046511104
%N Triangle read by rows: T(n,k) is the number of colored digraphs on n nodes with exactly k colors assigned in a fix order according the node count (1 <= k <= n).
%C The values are just subtotals of the rows of the irregular triangle A328773.
%C Colors C_1,...,C_k are assigned to n nodes in the way that a_i >= a_(i+1) >= 1 for 1 <= i < k, where a_i denotes the number of nodes colored with C_i.
%C T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
%C The order of the colors effects, that only one color scheme has to be considered for a given color count. If such an order may not be presupposed, you should note A329546.
%F T(n,1) = A000273(n) = A328773(n,1).
%F T(n,n) = 2^(n^2-n) = A053763(n) = A328773(n,A000041(n)).
%F T(n,n-1) = A328773(n,A000041(n)-1).
%F T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition p with k=#p} A328773(n,i).
%e Partitions for n=4, k=2: [3,1] and [2,2] with indices 2 and 3: T(4,2) = Sum_{i=2,3} A328773(4,i) = 752 + 1104 = 1856.
%e Partitions for n=6, k=3: [4,1,1], [3,2,1], [2,2,2] with indices 4, 6, 8: T(6,3) = Sum_{i=4,6,8} A328773(6,i) = 45277312 + 90196736 + 135032832 = 270506880.
%e Triangle T(n,k) begins:
%e 1
%e 3 4
%e 16 36 64
%e 218 1856 2112 4096
%e 9608 136376 445440 528384 1048576
%e 1540944 62020640 270506880 449511424 537919488 1073741824
%e ...
%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 Row(n)={[vecsum(apply(C, 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). A329546 (digraphs with unordered colors).
%K nonn,tabl
%O 1,2
%A _Peter Dolland_, Nov 16 2019
|
