cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A330693 Regular subtriangle of A328773: T(n,k) is the number of the balanced colored digraphs on n nodes with k colors, 1 <= k <= n.

Original entry on oeis.org

1, 3, 4, 16, 36, 64, 218, 1104, 2112, 4096, 9608, 90416, 266496, 528384, 1048576, 1540944, 30194176, 135032832, 269500416, 537919488, 1073741824
Offset: 1

Views

Author

Peter Dolland, Dec 25 2019

Keywords

Comments

The color count, k, is a measure of the differentiation of the nodes: k = 1 means no differentiation at all, so we have A000273. k = n means all nodes are taken to be different, and we have A053763. With increasing differentiation T(n,k) < T(n,k+1) for 1 <= k < n.

Examples

			The balanced color scheme [2,2,2] has with A330661 the index 5 in A328773. So there are T(6,3) = A328773(6,5) = 135032832 digraphs with 6 nodes two each in the same color.
Triangle T(n,k) begins:
        1;
        3,        4;
       16,       36,        64;
      218,     1104,      2112,      4096;
     9608,    90416,    266496,    528384,   1048576;
  1540944, 30194176, 135032832, 269500416, 537919488, 1073741824;
  ...

Crossrefs

Cf. A328773, A330661, A000273, A053763.

Programs

  • PARI
    \\ here C(p) computes 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),p[#p]-p[1]<=1], , 4))}
{ for(n=1, 6, print(Row(n))) }

Formula

T(n,1) = A000273(n).
T(n,n) = A053763(n) = 2^(n^2 - n).
T(n,k) = A328773(n,A330661(n,k)).

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

Original entry on oeis.org

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

Views

Author

Peter Dolland, Nov 23 2019

Keywords

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.

Examples

			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.

Crossrefs

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

Programs

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

Formula

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

A309980 Number of binary relations on n unlabeled nodes that are neither reflexive nor antireflexive.

Original entry on oeis.org

0, 4, 72, 2608, 272752, 93847104, 110518842048, 454710381676032, 6640565658505128832, 348708024629593894001152, 66538376166308068986316241408, 46534722991725338264882258863095808, 120139253095727581744381043433138973706240, 1151909524447243687554850690730124812494959992832
Offset: 1

Views

Author

Peter Dolland, Nov 02 2019

Keywords

Comments

Also the number of colored digraphs on n unlabeled nodes with nodes of exactly two colors. (Understand "(x,x) in the relation" for several nodes x as a special color!)

Examples

			n=2: We label node 1 with (1,1) in the relation and node 2 with (2,2) not in the relation, and we have two differently labeled nodes and so a(2) = A053763(2) = 4.
n=3: We have exactly either one or two nodes x with (x,x) in the relation. In A328773 this labelings correspond to the color schemes [2,1] and [1,2], both represented by the column index 2. So we have a(3) = 2 * A328773(3,2) = 72.

Links

Crossrefs

Cf. A000595 (arbitrary binary relations), A000273 (digraphs, i.e. reflexive resp. antireflexive binary relations), A053763 (digraphs with distinguishing labeled nodes), A328773 (digraphs with given color scheme).

Programs

  • Mathematica
    permcount[v_] := Module[{m = 1, s = 0, k = 0, t}, For[i = 1, i <= Length[v], i++, t = v[[i]]; k = If[i > 1 && t == v[[i - 1]], k + 1, 1]; m *= t*k; s += t]; s!/m];
edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := Module[{s = 0}, Do[t = 2^edges[p]; s += t*(1 - 2^(1 - Length[p]))* permcount[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 14] (* Jean-François Alcover, Jan 08 2021, after Andrew Howroyd *)
  • PARI
    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])}
a(n) = {my(s=0); forpart(p=n, my(t=2^edges(p)); s+=t*(1 - 2^(1-#p))*permcount(p)); s/n!} \\ Andrew Howroyd, Nov 02 2019

Formula

a(n) = A000595(n) - 2 * A000273(n) for n >= 1.

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

Views

Author

Peter Dolland, Nov 16 2019

Keywords

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.

Examples

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

Crossrefs

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

Programs

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

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

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

Original entry on oeis.org

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
Offset: 1

Views

Author

Peter Dolland, Nov 16 2019

Keywords

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.

Examples

			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.

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

Programs

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

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

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

Original entry on oeis.org

1, 1, 7, 116, 8282, 2168384, 2395241200, 10025552678528, 170709896192664592, 11335779739243176963200, 3029239690552322424003098368
Offset: 0

Views

Author

Peter Dolland, Nov 16 2019

Keywords

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
a(n) gives the number of digraphs (see A000273) without restrictions, where nodes of the same color are not differentiated.

Crossrefs

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

Programs

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

Formula

a(n) = Sum_{i=1..A000041(n)} A328773(n,i).
a(n) = Sum_{i=1..n} A329541(n,i) for n>=1.
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.