login
A329546
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).
2
1, 3, 4, 16, 72, 64, 218, 2608, 6336, 4096, 9608, 272752, 1336320, 2113536, 1048576, 1540944, 93847104, 812045184, 2337046528, 2689597440, 1073741824, 882033440, 110518842048, 1580861402112, 7344135176192, 14676310097920, 13200581984256, 4398046511104
OFFSET
1,2
COMMENTS
The values are weighted subtotals of the rows of the irregular triangle A328773.
The weight of a color scheme is the multiplicity A072811(n,k) with k as the index of the induced partition.
T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
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.
FORMULA
T(n,1) = A000273(n) = A328773(n,1).
T(n,n) = A053763(n) = A328773(n,A000041(n)).
T(n,n-1) = (n-1)*A328773(n,A000041(n)-1).
T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition with k elements} A072811(n,i)*A328773(n,i).
EXAMPLE
First six rows:
1
3 4
16 72 64
218 2608 6336 4096
9608 272752 1336320 2113536 1048576
1540944 93847104 812045184 2337046528 2689597440 1073741824
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.
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.
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)
Row(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n), #p==m], , 4))) | m<-[1..n]]}
{ for(n=0, 10, print(Row(n))) }
CROSSREFS
Cf. A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme).
Cf. A072811 (multiplicity of color schemes).
Cf. A329541 (ordered colors).
Cf. A309980 (reflexive/anti-reflexive: just two colors).
Sequence in context: A188116 A300316 A375471 * A057542 A353155 A252606
KEYWORD
nonn,tabl
AUTHOR
Peter Dolland, Nov 16 2019
STATUS
approved