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!)
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 (list; table; graph; refs; listen; history; text; internal format)
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.

LINKS

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

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: A188114 A188116 A300316 * A057542 A252606 A248240

Adjacent sequences:  A329543 A329544 A329545 * A329547 A329548 A329549

KEYWORD

nonn,tabl

AUTHOR

Peter Dolland, Nov 16 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 February 21 03:02 EST 2020. Contains 332086 sequences. (Running on oeis4.)