A329543 Number of colored digraphs on n nodes with 1 to n colors assigned in a fixed order according the node count.

1, 1, 7, 116, 8282, 2168384, 2395241200, 10025552678528, 170709896192664592, 11335779739243176963200, 3029239690552322424003098368

Offset

0,3

Comments

The values are just the row sums of the irregular triangle A328773 and for n>=1 of the regular triangle A329541.

Colors C_1,...,C_n are assigned to n nodes in the way that a_i >= a_(i+1) >= 0 for 1<=i<n, where a_i denotes the number of nodes colored with C_i.

a(n) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.

Links

Table of n, a(n) for n=0..10.

Formula

a(n) = Sum_{i=1..A000041(n)} A328773(n,i).

a(n) = Sum_{i=1..n} A329541(n,i) for n>=1.

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)={apply(C, vecsort([Vecrev(p) | p<-partitions(n)], , 4))}
{ for(n=0, 10, print(vecsum(Row(n)))) }

Crossrefs

Cf. A000041, A000273 (digraphs with one color), A053763 (digraphs with n colors), A328773 (digraphs to a given color scheme), A329541.

Sequence in context: A376042 A251585 A320083 * A180203 A070067 A027502

Adjacent sequences: A329540 A329541 A329542 * A329544 A329545 A329546

Keyword

nonn,more

Author

Peter Dolland, Nov 16 2019

Status

approved