A052283 -id:A052283 - cp's OEIS frontend

A000273 Number of unlabeled simple digraphs with n nodes.

1, 1, 3, 16, 218, 9608, 1540944, 882033440, 1793359192848, 13027956824399552, 341260431952972580352, 32522909385055886111197440, 11366745430825400574433894004224, 14669085692712929869037096075316220928, 70315656615234999521385506555979904091217920

Offset: 0

N. J. A. Sloane

CRC Handbook of Combinatorial Designs, 1996, p. 651.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 522.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 225.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 124, Table 5.1.2 and p. 241, Table A4.
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sept. 15, 1955, pp. 14-22.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Keith Briggs, Table of n, a(n) for n = 0..64
R. Absil and H Mélot, Digenes: genetic algorithms to discover conjectures about directed and undirected graphs, arXiv preprint arXiv:1304.7993 [cs.DM], 2013.
Fatemeh Arbabjolfaei and Young-Han Kim, Fundamentals of Index Coding, Foundations and Trends in Communications and Information Theory (2018) Vol. 14, Issue 3-4.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
A. Iványi, Leader election in synchronous networks, Acta Univ. Sapientiae, Mathematica, 5, 2 (2013) 54-82.
Gábor Kusper, Zijian Győző Yang, and Benedek Nagy, Using extended resolution to represent strongly connected components of directed graphs, Ann. Math. Inf. (2023).
M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
J. Qian, Enumeration of unlabeled directed hypergraphs, Electronic Journal of Combinatorics, 20(1) (2013), #P46. - From _N. J. A. Sloane_, Mar 01 2013
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
L. Travis, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.
Eric Weisstein's World of Mathematics, Simple Directed Graph
Index entries for "core" sequences

Row sums of A052283 and of A217654.

with(combinat):with(numtheory):
for n from 0 to 20 do p:=partition(n):
s:=0:for k from 1 to nops(p) do
q:=convert(p[k],multiset):
for i from 1 to n do a(i):=0:od:for i from 1 to nops(q) do a(q[i][1]):=q[i][2]:od:
c:=1:ord:=1:for i from 1 to n do c:=c*a(i)!*i^a(i): if a(i)<>0 then ord:=lcm(ord,i):fi:od:
g:=0:for d from 1 to ord do if ord mod d=0 then g1:=0:for del from 1 to d do if del<=n and d mod del=0 then g1:=g1+del*a(del):fi:od:g:=g+phi(ord/d)*g1*(g1-1):fi:od:
s:=s+2^(g/ord)/c:
od:
print(n,s):
od:
# Vladeta Jovovic, Jun 06 2006
# second Maple program:
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:
A000273 := n-> b(n$2, []):
seq(A000273(n), n=0..20);  # Alois P. Heinz, Sep 04 2019

Table[CycleIndex[PairGroup[SymmetricGroup[n],Ordered],t]/.Table[t[i]->1+x^i,{i,1,n^2}]/.{x->1},{n,1,7}] (* or *)
  Table[GraphPolynomial[n,t,Directed]/.{t->1},{n,1,20}]
(* 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]*2^edges[p], {p, IntegerPartitions[n]} ]; s/n!);
Table[a[n], {n, 0, 20}] (* 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)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from math import gcd, factorial
from sympy.utilities.iterables import partitions
def permcount(v):
    m, s, k = 1, 0, 0
    for i, t in enumerate(v):
        k = k+1 if i > 0 and t == v[i-1] else 1; m *= t*k; s += t
    return factorial(s)//m
def edges(v): return sum(sum(2*gcd(v[i], v[j]) for j in range(i)) for i in range(1, len(v))) + sum(vi-1 for vi in v)
def a(n):
    s = 0
    for p in partitions(n):
        pvec = []
        for i in sorted(p): pvec.extend([i]*p[i])
        s += permcount(pvec)*2**edges(pvec)
    return s//factorial(n)
print([a(n) for n in range(15)]) # Michael S. Branicky, Nov 14 2022 after Andrew Howroyd

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

a(n) ~ 2^(n*(n-1))/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016

More terms from Vladeta Jovovic, Dec 14 1999

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Original entry on oeis.org

1, 1, 0, 3, 4, 4, 1, 1, 0, 0, 8, 22, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 27, 108, 326, 667, 1127, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 0, 91, 582, 2432, 7694, 19646, 42148, 77305, 122953, 170315, 206982, 220768, 207301, 171008

Offset: 2

Vladeta Jovovic, Apr 21 2000

			1,1;
0,3,4,4,1,1;
0,0,8,22,37,47,38,27,13,5,1,1;
the last batch giving the numbers of connected digraphs with 4 nodes and from 1 to 12 arcs.

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

Andrew Howroyd, Table of n, a(n) for n = 2..2661 (rows 2..20)
R. J. Mathar, Statistics on Small Graphs, arXiv:1709.09000 (2017) Table 75.

Cf. A000238 (leading diagonal), A003085 (row sums), A053454 (column sums), A062735 (labeled).

Cf. A052283 (not necessarily connected), A283753 (another version), A057276 (strongly connected), A350789 (transpose).

InvEulerMTS(p)={my(n=serprec(p,x)-1, q=log(p), vars=variables(p)); sum(i=1, n, moebius(i)*substvec(q + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i)}
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, my(c=v[i]); t(c)^(c-1))}
G(n, x)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); s/n!}
row(n)={Vecrev(polcoef(InvEulerMTS(sum(i=0, n, G(i, y)*x^i, O(x*x^n))), n)/y)}
{ for(n=2, 6, print(row(n))) } \\ Andrew Howroyd, Jan 28 2022

A123554 Triangle read by rows: T(n,k) = number of labeled loopless digraphs with n nodes and k arcs (n >= 1, 0 <= k <= n*(n-1)).

Original entry on oeis.org

1, 1, 2, 1, 1, 6, 15, 20, 15, 6, 1, 1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1, 1, 20, 190, 1140, 4845, 15504, 38760, 77520, 125970, 167960, 184756, 167960, 125970, 77520, 38760, 15504, 4845, 1140, 190, 20, 1, 1, 30, 435, 4060, 27405, 142506, 593775

Offset: 1

N. J. A. Sloane, Nov 15 2006

			Triangle begins:
1
1 2 1
1 6 15 20 15 6 1
1 12 66 220 495 792 924 792 495 220 66 12 1

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 521.

G. C. Greubel, Table of n, a(n) for the first 25 rows, flattened

Row sums are A053763.

Cf. A052283 (unlabeled analog).

Table[CoefficientList[Series[(1+x)^(2*Binomial[n,2]), {x,0,2*Binomial[n,2]}], x], {n,6}] (* Geoffrey Critzer, Nov 12 2011 *)

T(n,k)={binomial(n*(n-1), k)}
{for(n=1, 5, for(k=0, n*(n-1), print1(T(n,k), ", ")); print)} \\ Andrew Howroyd, Apr 19 2020

T(n,k) = binomial(n*(n-1), k). - Andrew Howroyd, Apr 19 2020

More terms from Vladeta Jovovic, Nov 15 2006

A350908 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled unisolated nodes with k arcs, k = 0..n*(n-1).

Original entry on oeis.org

0, 0, 1, 1, 0, 0, 3, 4, 4, 1, 1, 0, 0, 1, 9, 23, 37, 47, 38, 27, 13, 5, 1, 1, 0, 0, 0, 3, 34, 116, 331, 669, 1128, 1477, 1665, 1489, 1154, 707, 379, 154, 61, 16, 5, 1, 1, 0, 0, 0, 1, 15, 134, 664, 2535, 7796, 19719, 42193, 77324, 122960, 170317, 206983, 220768

Offset: 1

Andrew Howroyd, Jan 28 2022

			Triangle begins:
  [1] 0;
  [2] 0, 1, 1;
  [3] 0, 0, 3, 4,  4,  1,  1;
  [4] 0, 0, 1, 9, 23, 37, 47, 38, 27, 13, 5, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..2680 (rows 1..20)

Row sums are A053598.
Column sums are A053418.
The labeled version is A054547.
Cf. A052283, A054733.

\\ See A054733 for G.
row(n)={Vecrev(G(n,y)-G(n-1,y), n*(n-1)+1)}
{ for(n=1, 6, print(row(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

A126066 Triangle read by rows: T(n,k) is the number of unlabeled digraphs on n nodes with k arcs up to reversing the arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 4, 9, 18, 24, 30, 24, 18, 9, 4, 1, 1, 1, 1, 4, 11, 38, 89, 210, 382, 616, 787, 880, 787, 616, 382, 210, 89, 38, 11, 4, 1, 1, 1, 1, 4, 12, 48, 165, 567, 1703, 4623, 10836, 22273, 39866, 62650, 86209, 104456, 111256, 104456, 86209, 62650, 39866, 22273, 10836, 4623, 1703, 567, 165, 48, 12, 4, 1, 1

Offset: 0

Vladeta Jovovic, Feb 28 2007

			Triangle begins:
  1;
  1;
  1,1,1;
  1,1,3,3,3,1,1;
  1,1,4,9,18,24,30,24,18,9,4,1,1;
  ...
G.f. for fourth row is obtained if we set x(i) = 1+x^i, i=1..12 in (1/48)*(x(1)^12+12*x(1)^2*x(2)^5+4*x(2)^6+8*x(3)^4+12*x(4)^3+3*x(1)^4*x(2)^4+8*x(6)^2)

Andrew Howroyd, Table of n, a(n) for n = 0..2680 (rows 0..20)

Row sums give A054933.

Cf. A052283, A126066.

T(n,k) = (A052283(n,k) + A126066(n,k))/2. - Andrew Howroyd, Apr 20 2020

a(0)=1 prepended and terms a(64) and beyond from Andrew Howroyd, Apr 20 2020

A126067 Triangle read by rows: T(n,k) is the number of unlabeled self-converse digraphs with n nodes and k arcs, k=0..n*(n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 3, 5, 9, 10, 12, 10, 9, 5, 3, 1, 1, 1, 1, 3, 6, 15, 24, 41, 57, 77, 84, 90, 84, 77, 57, 41, 24, 15, 6, 3, 1, 1, 1, 1, 3, 7, 20, 42, 91, 164, 295, 463, 683, 918, 1185, 1394, 1550, 1590, 1550, 1394, 1185, 918, 683, 463, 295, 164, 91, 42, 20, 7, 3, 1, 1

Offset: 0

Vladeta Jovovic, Feb 28 2007

			Triangle begins:
  1;
  1;
  1,1,1;
  1,1,2,2,2,1,1;
  1,1,3,5,9,10,12,10,9,5,3,1,1;
  1,1,3,6,15,24,41,57,77,84,90,84,77,57,41,24,15,6,3,1,1;
  ....

Andrew Howroyd, Table of n, a(n) for n = 0..2680 (rows 0..20)

Row sums are A002499.

Cf. A052283, A126066.

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(c=gcd(v[i], v[j])*if(v[i]*v[j]%2==0, 2, 1)); t(2*v[i]*v[j]/c)^c)) * prod(i=1, #v, my(c=v[i]); if(c%2, t(2*c)^(c\2), t(c)^(c-1-c%4/2)*t(c/2)^(c%4)))}
Row(n) = {my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+x^i)); Vecrev(s)/n!}
{ for(n=0, 5, print(Row(n))) } \\ Andrew Howroyd, Apr 19 2020

a(0)=1 prepended and terms a(46) and beyond from Andrew Howroyd, Apr 19 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

cp's OEIS Frontend

A000273 Number of unlabeled simple digraphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

Extensions

A054733 Triangle of number of (weakly) connected unlabeled digraphs with n nodes and k arcs (n >=2, k >= 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

A123554 Triangle read by rows: T(n,k) = number of labeled loopless digraphs with n nodes and k arcs (n >= 1, 0 <= k <= n*(n-1)).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A350908 Triangle read by rows: T(n,k) is the number of digraphs on n unlabeled unisolated nodes with k arcs, k = 0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

Crossrefs

Programs

PARI

A126066 Triangle read by rows: T(n,k) is the number of unlabeled digraphs on n nodes with k arcs up to reversing the arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A126067 Triangle read by rows: T(n,k) is the number of unlabeled self-converse digraphs with n nodes and k arcs, k=0..n*(n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

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

Views