A329546 -id:A329546 - cp's OEIS frontend

A329874 Array read by antidiagonals: A(n,k) = number of digraphs on n unlabeled nodes, arbitrarily colored with k given colors (n >= 1, k >= 1).

1, 2, 3, 3, 10, 16, 4, 21, 104, 218, 5, 36, 328, 3044, 9608, 6, 55, 752, 14814, 291968, 1540944, 7, 78, 1440, 45960, 2183400, 96928992, 882033440, 8, 105, 2456, 111010, 9133760, 1098209328, 112282908928, 1793359192848

Offset: 1

Peter Dolland, Nov 23 2019

The coloring of nodes is unrestricted. There is no constraint that all of the k colors have to be used. Nodes with different colors are counted as distinct, nodes with the same color are not. For digraphs with a fixed color set see A329546.

			First six rows and columns:
      1        2          3          4           5           6
      3       10         21         36          55          78
     16      104        328        752        1440        2456
    218     3044      14814      45960      111010      228588
   9608   291968    2183400    9133760    27755016    68869824
1540944 96928992 1098209328 6154473664 23441457680 69924880288
...
n=4, k=3 with A329546:
A(4,3) = 3*218 + 3*2608 + 6336 = 14814.

Cf. A000273 digraphs with one color, A000595 binary relations, A329546 digraphs with exactly k colors, A328773 digraphs with a given color scheme.

\\ 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)
A329546(n)={[vecsum(apply(wC, vecsort([Vecrev(p) | p<-partitions(n),#p==m], , 4))) | m<-[1..n]]}
Row(n)=vector(6, k, binomial(k)[2..min(k,n)+1]*A329546(n)[1..min(k,n)]~)
{ for(n=0, 6, print(Row(n))) }

A(1,k) = k.
A(2,k) = k*(2*k+1).
A(n,1) = A000273(n).
A(n,2) = A000595(n).
A(n,4) = A353996(n+1). - Brendan McKay, May 13 2022
A(n,k) = Sum_{i=1..min(n,k)} binomial(k,i)*A329546(n,i).

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).

Original entry on oeis.org

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

Offset: 1

Peter Dolland, Nov 16 2019

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.

			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
  ...

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

\\ 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))) }

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).

cp's OEIS Frontend

A329874 Array read by antidiagonals: A(n,k) = number of digraphs on n unlabeled nodes, arbitrarily colored with k given colors (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula