login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 0
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..36.

FORMULA

A(1,k) = k.

A(2,k) = k*(2*k+1).

A(n,1) = A000273(n).

A(n,2) = A000595(n).

A(n,k) = Sum_{i=1..min(n,k)} binomial(k,i)*A329546(n,i).

EXAMPLE

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.

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)

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

CROSSREFS

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

Sequence in context: A100652 A094416 A218868 * A152300 A117030 A155758

Adjacent sequences:  A329871 A329872 A329873 * A329875 A329876 A329877

KEYWORD

nonn,tabl

AUTHOR

Peter Dolland, Nov 23 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 10:24 EST 2020. Contains 331193 sequences. (Running on oeis4.)