A000273 -id:A000273 - cp's OEIS frontend

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

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

Peter Dolland, Nov 16 2019

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.

			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.

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

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

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

A343592 Number of symmetry types of digraphs with n nodes.

Original entry on oeis.org

1, 2, 4, 9, 14, 36

Offset: 1

Peter Dolland, Apr 21 2021

The symmetry type of a digraph is determined by its automorphism group. It is a permutation group on the nodes set, and therefore a subgroup of the symmetric group Sn. The total number of these is determined by A000638. But not all of them occur as an automorphism group of a digraph.

			The four symmetry types of the digraphs with 3 nodes are represented by:
1.) {}, the empty graph, has together with the full graph the automorphism group S_3 (as subgroup of S_3) as symmetry type.
2.) {(1,2)} has together with 6 other digraphs the trivial automorphism group {id} as symmetry type. This digraph class is called asymmetric. Their values are given by A051504.
3.) {(1,2),(2,1)} has together with 5 other digraphs the automorphism group containing id and a transposition (so it is C_2 as the subgroup of S_3) as symmetry type.
4.) {(1,2),(2,3),(3,1)} has as the only digraph with three nodes the automorphism group C_3 as symmetry type. As a consequence it has to be self-complementary.
The total of the sizes of the symmetry type classes yields the number of digraphs A000273. Here: 2+7+6+1 = 16 = A000273(3).
Note, that for n > 3 there may be different symmetry types with isomorphic automorphism groups. For n=4 both {(1,2)} and {(1,2),(3,4)} have C_2 as automorphism group, but they are different as permutation group.

Peter Dolland, Digraph Symmetry Tables for n = 3..6
Götz Pfeiffer, Subgroups. [broken link]

Cf. A000273, A000638, A051504, A053763, A000595.

A350911 Number of regular digraphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 3, 6, 11, 56, 609, 39346, 8728237, 6126648298, 14487876826313

Offset: 0

Andrew Howroyd, Jan 29 2022

Row sums of A350910.

Cf. A000273, A005176, A329234, A350913.

A361583 Number of digraphs on n unlabeled nodes whose strongly connected components are complete digraphs.

Original entry on oeis.org

1, 1, 3, 12, 88, 1217, 34672, 2039085, 246005109, 60296886108, 29828186693218, 29663937774464786, 59172529527454608139, 236453014376786629601848, 1891427400988740573006253862, 30274661556583530830890359188257, 969429810937979825934973090455224882

Offset: 0

Andrew Howroyd, Mar 16 2023

nonn

The labeled version is A361560.

Cf. A000273, A350794, A361584, A361585.

A361583seq(16) \\ See PARI link in A350794 for program code.

A054918 Number of connected unlabeled digraphs with n nodes such that complement is also connected.

Original entry on oeis.org

1, 1, 10, 180, 9120, 1520742, 878908844, 1791588717764, 13024366540532952, 341234368845828951004, 32522226812040344643993088, 11366680383641301437820379768750, 14669062959091969068110415719779627436

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A003085.

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003085 = Cases[Import["https://oeis.org/A003085/b003085.txt", "Table"], {, }][[All, 2]];
a[n_] := 2*A003085[[n]] - A000273[[n + 1]];
Array[a, 50] (* Jean-François Alcover, Aug 31 2019 *)

from functools import lru_cache
from itertools import product, combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A054918(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

a(n) = 2*A003085(n) - A000273(n).

More terms from Vladeta Jovovic, Jul 19 2000

A054932 Number of unlabeled connected digraphs up to complementarity.

Original entry on oeis.org

1, 1, 7, 95, 4628, 760731, 439476534, 895794710762, 6512183359880844, 170617184427498641390, 16261113406024864291983616, 5683340191820651519596089554647, 7334531479545984537334675978032833750, 35157813638509073199087893774184443496308877

Offset: 1

N. J. A. Sloane, May 24 2000

Andrew Howroyd, Table of n, a(n) for n = 1..50
V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Cf. A000273, A003085, A003086, A054931.

A054932 := proc(n)
    A003085(n)-(A000273(n)-A003086(n))/2 ;
end proc:
seq(A054932(n),n=1..13) ; # R. J. Mathar, Mar 04 2018

A000273 = Cases[Import["https://oeis.org/A000273/b000273.txt", "Table"], {, }][[All, 2]];
A003085 = Cases[Import["https://oeis.org/A003085/b003085.txt", "Table"], {, }][[All, 2]];
A003086 = Cases[Import["https://oeis.org/A003086/b003086.txt", "Table"], {, }][[All, 2]];
a[n_] := A003085[[n]] - (A000273[[n + 1]] - A003086[[n]])/2;
Array[a, 50] (* Jean-François Alcover, Sep 01 2019 *)

a(n) = A003085(n) - (A000273(n)-A003086(n))/2. - Andrew Howroyd, Sep 17 2018

Terms a(14) and beyond from Andrew Howroyd, Sep 17 2018

A067309 Number of symmetric unlabeled digraphs (unlabeled digraphs with nontrivial automorphism group).

Original entry on oeis.org

0, 0, 2, 9, 82, 1607, 95647, 18545153

Offset: 0

Labos Elemer, Jan 11 2002

			For n=4 nodes from the 218 (=A000273(4)) unlabeled nonisomorphic digraphs 136 (=A051504(4)) are asymmetric, so 218 - 136 = 82 are somehow symmetric.

Cf. A000273, A051504.

a(n) = A000273(n) - A051504(n).

a(7) added using nauty by Andrew Howroyd, Dec 06 2020

A199012 The total number of edges in all unlabeled directed graphs (no self loops allowed) on n nodes.

Original entry on oeis.org

0, 3, 48, 1308, 96080, 23114160, 18522702240, 50214057399744, 469006445678383872, 15356719437883766115840, 1788760016178073736115859200, 750205198434476437912637004278784, 1144188684031608529784893493874665232384, 6398724751986384956446081096594171272300830720

Offset: 1

Geoffrey Critzer, Nov 01 2011

nonn

Cf. A000273, A052283, A086314.

b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(p[j]-1+add(
      igcd(p[k], p[j]), k=1..j-1)*2, j=1..nops(p)))([l[], 1$n])),
      add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, [])*n*(n-1)/2:
seq(a(n), n=1..16);  # Alois P. Heinz, Sep 04 2019

Table[D[GraphPolynomial[n,x,Directed],x]/.x->1, {n,1,15}]
(* Second program: *)
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_, t_] := Product[g = GCD[v[[i]], v[[j]]]; t[v[[i]]*v[[j]]/g]^(2*g), {i, 2, Length[v]}, {j, 1, i - 1}] * Product[ t[v[[i]]]^(v[[i]] - 1), {i, 1, Length[v]}]
a[n_] := (s = 0; Do[s += permcount[p]*(D[edges[p, 1 + x^# &], x] /. x -> 1), {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)

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,t) = {prod(i=2, #v, prod(j=1, i-1, my(g=gcd(v[i],v[j])); t(v[i]*v[j]/g)^(2*g))) * prod(i=1, #v, t(v[i])^(v[i]-1))}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*subst(deriv(edges(p,i->1+x^i)),x,1)); s/n!} \\ Andrew Howroyd, Nov 05 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A199012(n): return (n*(n-1)>>1)*int(sum(Fraction(1<Chai Wah Wu, Jul 05 2024

a(n) = A000273(n) * n(n-1)/2.

a(n) = Sum_{k=1..n*(n-1)} k*A052283(n,k). - Andrew Howroyd, Nov 05 2017

A222420 Number of unlabeled general directed hypergraphs of order n.

Original entry on oeis.org

2, 10, 752, 179228736, 10074382205972351614976

Offset: 1

N. J. A. Sloane, Mar 01 2013

			The 10 non-isomorphic directed hypergraphs of order 2 are as follows (these are their arc sets): {<1,0>, <2,0>}, {<1, {2}>, <2, {1}>}, {<1, {2}>, <1,0>, <2, {1}>, <2,0>}, {<1, {2}>}, {<1, {2}>, <1,0>}, {<1, {2}>, <1,0>, <2, {1}>}, {<1,0>}, {<1, {2}>, <2,0>}, {<1, {2}>, <1,0>, <2,0>}, 0.

J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), #P46.

Cf. A000273, A222421.

A222421 Number of unlabeled 3-uniform directed hypergraphs of order n.

Original entry on oeis.org

1, 1, 4, 218, 8978144, 1601285885249024, 8048575244466823237217930240

Offset: 1

N. J. A. Sloane, Mar 01 2013

J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), #P46.

Cf. A000273, A222420.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A343592 Number of symmetry types of digraphs with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A350911 Number of regular digraphs on n unlabeled nodes.

Views

Author

Keywords

Crossrefs

A361583 Number of digraphs on n unlabeled nodes whose strongly connected components are complete digraphs.

Views

Author

Keywords

Crossrefs

Programs

PARI

A054918 Number of connected unlabeled digraphs with n nodes such that complement is also connected.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A054932 Number of unlabeled connected digraphs up to complementarity.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A067309 Number of symmetric unlabeled digraphs (unlabeled digraphs with nontrivial automorphism group).

Views

Author

Keywords

Examples

Crossrefs

Formula

Extensions

A199012 The total number of edges in all unlabeled directed graphs (no self loops allowed) on n nodes.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A222420 Number of unlabeled general directed hypergraphs of order n.

Views

Author

Keywords

Examples

Links

Crossrefs

A222421 Number of unlabeled 3-uniform directed hypergraphs of order n.