|
| |
|
|
A329541
|
|
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).
|
|
2
|
|
|
|
1, 3, 4, 16, 36, 64, 218, 1856, 2112, 4096, 9608, 136376, 445440, 528384, 1048576, 1540944, 62020640, 270506880, 449511424, 537919488, 1073741824, 882033440, 55259421024, 435010671104, 1101584588800, 1834672455680, 2200096997376, 4398046511104
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The values are just subtotals of the rows of the irregular triangle A328773.
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.
T(n,k) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.
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.
|
|
|
LINKS
|
Table of n, a(n) for n=1..28.
|
|
|
FORMULA
|
T(n,1) = A000273(n) = A328773(n,1).
T(n,n) = 2^(n^2-n) = A053763(n) = A328773(n,A000041(n)).
T(n,n-1) = A328773(n,A000041(n)-1).
T(n,k) = Sum_{i=1..A000041(n), A063008(n,i) encodes a partition p with k=#p} A328773(n,i).
|
|
|
EXAMPLE
|
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.
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.
Triangle T(n,k) begins:
1
3 4
16 36 64
218 1856 2112 4096
9608 136376 445440 528384 1048576
1540944 62020640 270506880 449511424 537919488 1073741824
...
|
|
|
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, [])}
Row(n)={[vecsum(apply(C, 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). A329546 (digraphs with unordered colors).
Sequence in context: A251582 A328773 A330693 * A154736 A188114 A188116
Adjacent sequences: A329538 A329539 A329540 * A329542 A329543 A329544
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Peter Dolland, Nov 16 2019
|
|
|
STATUS
|
approved
|
| |
|
|
