A000273 -id:A000273 - cp's OEIS frontend

A053467 Number of directed 2-multigraphs on n nodes.

1, 6, 138, 22815, 29197989, 286181094816, 21712697070199704, 12980080058620326927885, 62082385554465497895132149640, 2405193620328895144597707267893468286, 762399006478986275307113015668690102196187810

Offset: 1

Vladeta Jovovic, Jan 13 2000

A 2-multigraph is similar to an ordinary graph except there are 0, 1 or 2 edges between any two nodes (self-loops are not allowed).

Andrew Howroyd, Table of n, a(n) for n = 1..40

Cf. A000273, A053468.

Table[CycleIndex[PairGroup[SymmetricGroup[n], Ordered], t] /.Table[t[i] -> 1 + x^i + y^i, {i, 1, n^2}] /. {x -> 1, y -> 1}, {n, 1, 7}] (* Geoffrey Critzer, Mar 08 2011 *)
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 - 1];
a[n_] := (s=0; Do[s += permcount[p]*3^edges[p], {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) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053467(n): return int(sum(Fraction(3**((sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))<<1)+sum(q*r**2 for q, r in p.items())-s),prod(q**r*factorial(r) for q, r in p.items())) for s, p in partitions(n,size=True))) # Chai Wah Wu, Jul 10 2024

a(11) from Andrew Howroyd, Oct 22 2017

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Original entry on oeis.org

1, 2, 6, 24, 160, 2512, 129816, 22665792, 13056562208, 24953006054144, 160860329639968800, 3555065836569542246400, 273147301191314006316868352, 73832333258502021627712839197696, 70920540648597652305602460997787710080, 244186544390677638132290202415190606165938176, 3036252267734950687777830287721323374283100639476736

Offset: 0

Brendan McKay, May 11 2019

Eulerian means that for every vertex the in-degree equals the out-degree.

			For n=2 the a(2)=6 solutions are: two non-adjacent vertices with or without loops (3 cases), two vertices with or without loops connected by edges in each direction (3 cases).

Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Eulerian digraphs with loops.

For labeled digraphs rather than isomorphism classes see A229865.
For isomorphism classes with loops forbidden see A058338.
Cf. A308128 (connected version of this).
Cf. A000273, A000595, A002416, A002720, A308161.

Euler transform of A308128.

Terms a(10) and beyond from Andrew Howroyd, Apr 12 2020

A053468 Number of directed 3-multigraphs on n nodes.

Original entry on oeis.org

1, 10, 720, 703760, 9168331776, 1601371799340544, 3837878966366932639744, 128777257564337108286016980992, 61454877497308462618188532330410573824, 422314689395950135433730499958070655419345928192

Offset: 1

Vladeta Jovovic, Jan 13 2000

Andrew Howroyd, Table of n, a(n) for n = 1..40
Rebekka Willenberg, Self-Complementary Graphs and Digraphs. In search of a natural bijection, 2017.

Cf. A000273, A053467, A000171, A003086.

Table[CoefficientList[PairGroupIndex[SymmetricGroup[n],s,Ordered]/.Table[s[i]->4,{i,1,2 Binomial[n,2]}],x],{n,1,8}] (* Geoffrey Critzer, Oct 20 2012 *)
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 - 1];
a[n_] := (s=0; Do[s += permcount[p]*4^edges[p], {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) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i]-1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*4^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053468(n): return int(sum(Fraction(1<<((sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))<<1)+sum(q*r**2 for q, r in p.items())-s<<1),prod(q**r*factorial(r) for q, r in p.items())) for s, p in partitions(n,size=True))) # Chai Wah Wu, Jul 10 2024

a(n) = A003086(2n) = A000171(4n). - Andrey Zabolotskiy, Feb 21 2021

A361582 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 5, 5, 6, 0, 83, 62, 42, 31, 0, 5048, 2494, 1172, 592, 302, 0, 1047008, 330063, 103961, 38312, 15616, 5984, 0, 705422362, 137934757, 28095923, 7243110, 2297690, 795930, 243668, 0, 1580348371788, 184557780045, 23226116293, 3951426731, 914429926, 261269562, 79512478, 20286025

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,       1;
  0,       1,      2;
  0,       5,      5,      6;
  0,      83,     62,     42,    31;
  0,    5048,   2494,   1172,   592,   302;
  0, 1047008, 330063, 103961, 38312, 15616, 5984;
  ...

Wikipedia, Strongly connected component.

Column k=1 is A035512.
Main diagonal is A003087.
Row sums are A000273.
The labeled version is A361455.
Cf. A106238, A350794, A361587, A361588.

\\ See PARI link in A350794 for program code.
{ my(A=A361582triang(6)); for(n=1, #A, print(A[n])) }

A051504 Number of asymmetric digraphs with n nodes.

Original entry on oeis.org

1, 1, 1, 7, 136, 8001, 1445297, 863488287

Offset: 0

Vladeta Jovovic

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 231.
P. K. Stockmeyer, The enumeration of graphs with prescribed automorphism group, Dissertation, Univ. of Michigan, Ann Arbor, 1971.

Cf. A000273 (digraphs), A003400 (asymmetric graphs), A030242 (asymmetric relations), A067309.

a(n) = A000273(n) - A067309(n). - Andrew Howroyd, Dec 06 2020

a(6) from Christian G. Bower Dec 15 1999

a(7) from Andrew Howroyd, Dec 06 2020

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Original entry on oeis.org

1, 2, 10, 114, 4872, 770832, 441038832, 896679948304, 6513978501814144, 170630215981070456064, 16261454692532635025585792, 5683372715412701087902846672384, 7334542846356464937798016155801130496, 35157828307617499760694672217473135511928832

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, A003086, A007869, A054960, A055969.

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 - 1];
b[n_] := (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
edges4[v_] := 4 Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[2 v[[i]] - 1, {i, 1, Length[v]}];
c[n_] := (s = 0; Do[s += permcount[2 p]*2^edges4[p]*If[OddQ[n], n *4^Length[p], 1], {p, IntegerPartitions[n/2 // Floor]}]; s/n!);
a[n_] := (b[n] + c[n])/2;
Array[a, 14] (* Jean-François Alcover, Aug 26 2019, using Andrew Howroyd's code for b=A000273 and c=A003086 *)

Average of A000273 and A003086.

More terms from Vladeta Jovovic, Jul 19 2000

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

A127909 Number of different digraphs on n unlabeled nodes which are not graphs.

Original entry on oeis.org

0, 0, 1, 12, 207, 9574, 1540788, 882032396, 1793359180502, 13027956824124884, 341260431952960575184, 32522909385055885092199576, 11366745430825400574268802831632, 14669085692712929869037045573284852976, 70315656615234999521385506526925748433982432

Offset: 0

Jonathan Vos Post, Feb 06 2007

A digraph is (isomorphic to) a graph if every pair of points a, b joined by a directed edge (a,b) also has the reverse directed edge (b,a). A digraph which is not a graph is a digraph with at least one pair of points which have only one directed edge connecting them.

			a(2) = 1 because with two points a and b, either there are no edges connecting them, or there is one directed edge between them, or there is a bidirectional pair of edges between them; only the case with one directed edge is the unique 2-point digraph which is not a graph.

Chai Wah Wu, Table of n, a(n) for n = 0..60

Cf. A000088, A000273, A127910-A127915.

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A127909(n): return int(sum(Fraction((1<>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 05 2024

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

A283753 Irregular triangular array read by rows: T(n,k) is the number of non-isomorphic unlabeled weakly connected digraphs on n nodes and with k arcs.

Original entry on oeis.org

1, 1, 1, 3, 4, 4, 1, 1, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008, 124110, 78813, 43862, 21209, 8951, 3242, 1043, 288, 76, 17, 5, 1, 1, 350, 3024, 17314, 74676, 266364, 808620, 2144407

Offset: 1

Marko Riedel, Mar 15 2017

The range for the subindex k is from n-1 to n(n-1).

Obtained from A054733 by removing leading zeros.

			First rows are:
1;
1,    1;
3,    4,   4,   1,    1;
8,   22,  37,  47,   38,   27,   13,    5,    1,   1;
27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, ...

E. Palmer and F. Harary, Graphical Enumeration, Academic Press, 1973.

Marko R. Riedel, Number of distinct connected digraphs
Marko Riedel, Maple code for sequences A052283, A283753.

Cf. A000273, A000238, A003085, A052283.

\\ See A054733 for G, InvEulerMTS.
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y^(n-1))}
{ for(n=1, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A329234 Number of digraphs on n unlabled vertices such that every vertex has the same outdegree.

Original entry on oeis.org

1, 1, 2, 4, 14, 107, 3080, 328126, 114236734, 141361169088, 565835083485352, 8280254429732072354, 401805920591472162735162, 73001963040583041357650757758, 44826822610575086782059677501403310, 104876792026574880566541471182849498480154, 841219618683014295050378892027503163229521608514

Offset: 0

Andrew Howroyd, Nov 08 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50

Row sums of A329228.

Cf. A000273.

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}
E(v, x) = {my(r=1/(1-x)); for(i=1, #v, r=serconvol(r, prod(j=1, #v, my(g=gcd(v[i], v[j])); (1 + x^(v[j]/g))^g)/(1 + x))); r}
a(n)={if(n<1, n==0, my(s=0); forpart(p=n, s+=permcount(p)*E(p, x+O(x^n))); vecsum(Vec(s))/n!)}

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

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

cp's OEIS Frontend

A053467 Number of directed 2-multigraphs on n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A053468 Number of directed 3-multigraphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A361582 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled nodes with k strongly connected components.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A051504 Number of asymmetric digraphs with n nodes.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions

A054928 Number of complementary pairs of directed graphs on n nodes. Also number of unlabeled digraphs with n nodes and an even number of arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A127909 Number of different digraphs on n unlabeled nodes which are not graphs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A283753 Irregular triangular array read by rows: T(n,k) is the number of non-isomorphic unlabeled weakly connected digraphs on n nodes and with k arcs.

Views

Author

Keywords

Comments

Examples

References

Links