A001174 -id:A001174 - cp's OEIS frontend

A000666 Number of symmetric relations on n nodes.

1, 2, 6, 20, 90, 544, 5096, 79264, 2208612, 113743760, 10926227136, 1956363435360, 652335084592096, 405402273420996800, 470568642161119963904, 1023063423471189431054720, 4178849203082023236058229792, 32168008290073542372004082199424

Offset: 0

N. J. A. Sloane

Each node may or may not be related to itself.
Also the number of rooted graphs on n+1 nodes.
The 1-to-1 correspondence is as follows: Given a rooted graph on n+1 nodes, replace each edge joining the root node to another node with a self-loop at that node and erase the root node. The result is an undirected graph on n nodes which is the graph of the symmetric relation.
Also the number of the graphs with n nodes whereby each node is colored or not colored. A loop can be interpreted as a colored node. - Juergen Will, Oct 31 2011

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 101, 241.
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.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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).

David Applegate, Table of n, a(n) for n = 0..80 [Shortened file because terms grow rapidly: see Applegate link below for additional terms]
David Applegate, Table of n, a(n) for n = 0..100
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.
R. L. Davis, Structure of dominance relations, Bull. Math. Biophys., 16 (1954), 131-140. [Annotated scanned copy]
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Am. Math. Soc. 78 (1955) 445-463, eq. (24).
Frank Harary, Edgar M. Palmer, Robert W. Robinson and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Adib Hassan, Po-Chien Chung and Wayne B. Hayes, Graphettes: Constant-time determination of graphlet and orbit identity including (possibly disconnected) graphlets up to size 8, arXiv:1708.04341 [cs.DS], 2017.
Mathematics Stack Exchange, Enumerating Graphs with Self-Loops, Jan 23 2014.
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.
W. Oberschelp, The number of non-isomorphic m-graphs, Presented at Mathematical Institute Oberwolfach, July 3 1967 [Scanned copy of manuscript]
W. Oberschelp, Strukturzahlen in endlichen Relationssystemen, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Marko Riedel, Maple code for sequence.
Marko Riedel et al., Enumerating Graphs with Self-Loops
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
Sage, Common Graphs (Graph Generators)
Lorenzo Sauras-Altuzarra, Graphs
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
Eric Weisstein's World of Mathematics, Rooted Graph

Cf. A000595, A001172, A001174, A006905, A000250, A054921 (connected relations).

Maple
```
# see Riedel link above
```

Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]], Permutations[Range[n*(n-1)/2+1, n*(n+1)/2]], 2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,8}]] (* Geoffrey Critzer, Nov 04 2011 *)
Table[Module[{eds,pms,leq},
eds=Select[Tuples[Range[n],2],OrderedQ];
pms=Map[Sort,eds/.Table[i->Part[#,i],{i,n}]]&/@Permutations[Range[n]];
leq=Function[seq,PermutationCycles[Ordering[seq],Length]]/@pms;
Total[Thread[Power[2,leq]]]/n!
],{n,0,8}] (* This is after Geoffrey Critzer's program but does not use the (deprecated) Combinatorica package. - Gus Wiseman, Jul 21 2016 *)
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[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
a[n_] := a[n] = (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Nov 13 2017, 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, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2 + 1)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000666(n): return int(sum(Fraction(1<>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 02 2024

Euler transform of A054921. - N. J. A. Sloane, Oct 25 2018
Let G_{n+1,k} be the number of rooted graphs on n+1 nodes with k edges and let G_{n+1}(x) = Sum_{k=0..n(n+1)/2} G_{n+1,k} x^k. Thus a(n) = G_{n+1}(1). Let S_n(x_1, ..., x_n) denote the cycle index for Sym_n. (cf. the link in A000142).
Compute x_1*S_n and regard it as the cycle index of a set of permutations on n+1 points and find the corresponding cycle index for the action on the n(n+1)/2 edges joining those points (the corresponding "pair group"). Finally, by replacing each x_i by 1+x^i gives G_{n+1}(x). [Harary]
Example, n=2. S_2 = (1/2)*(x_1^2+x_2), x_1*S_2 = (1/2)*(x_1^3+x_1*x_2). The pair group is (1/2)*(x_1^2+x_1*x_2) and so G_3(x) = (1/2)*((1+x)^3+(1+x)*(1+x^2)) = 1+2*x+2*x^2+x^3; set x=1 to get a(2) = 6.
a(n) ~ 2^(n*(n+1)/2)/n! [McIlroy, 1955]. - Vaclav Kotesovec, Dec 19 2016

Description corrected by Christian G. Bower
More terms from Vladeta Jovovic, Apr 18 2000
Entry revised by N. J. A. Sloane, Mar 06 2007

A000595 Number of binary relations on n unlabeled points.

Original entry on oeis.org

1, 2, 10, 104, 3044, 291968, 96928992, 112282908928, 458297100061728, 6666621572153927936, 349390545493499839161856, 66603421985078180758538636288, 46557456482586989066031126651104256, 120168591267113007604119117625289606148096, 1152050155760474157553893461743236772303142428672

Offset: 0

N. J. A. Sloane

Number of orbits under the action of permutation group S(n) on n X n {0,1} matrices. The action is defined by f.M(i,j)=M(f(i),f(j)).

Equivalently, the number of digraphs on n unlabeled nodes with loops allowed but no more than one arc with the same start and end node. - Andrew Howroyd, Oct 22 2017

			From _Gus Wiseman_, Jun 17 2019: (Start)
Non-isomorphic representatives of the a(2) = 10 relations:
  {}
  {1->1}
  {1->2}
  {1->1, 1->2}
  {1->1, 2->1}
  {1->1, 2->2}
  {1->2, 2->1}
  {1->1, 1->2, 2->1}
  {1->1, 1->2, 2->2}
  {1->1, 1->2, 2->1, 2->2}
(End)

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 76 (2.2.30)
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).

Jean-François Alcover, Table of n, a(n) for n = 0..50 (a(0)-a(37) from Charles R. Greathouse IV)
Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 274.
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Alberto Casagrande, Carla Piazza, and Alberto Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Preprint 2015.
Alexander Clow, Alfie Davies, and Neil Anderson McKay, Constructing All Birthday 3 Games as Digraphs, arXiv:2505.06206 [math.CO], 2025. See p. 13.
Matthew Dabkowski, N. Fan, and R. Breiger, Exploratory blockmodeling for one-mode, unsigned, deterministic networks using integer programming and structural equivalence, Social Networks, Volume 47, October 2016, Pages 93-106.
Robert L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Thomas M. A. Fink, Emmanuel Barillot, and Sebastian E. Ahnert, Dynamics of network motifs, 2006.
Frank Harary, Edgar M. Palmer, Robert W. Robinson, and Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
Sergiy Kozerenko, On the abstract properties of Markov graphs for maps on trees, Mathematical Bilten 41:2 (2017), pp. 5-21.
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ötz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Samuel Reid, On Generalizing a Temporal Formalism for Game Theory to the Asymptotic Combinatorics of S5 Modal Frames, arXiv preprint arXiv:1305.0064 [math.LO], 2013.
Marko Riedel, Counting nonisomorphic binary relations (includes Maple code).
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout
J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976
Leopold Travis, Graphical Enumeration: A Species-Theoretic Approach, arXiv:math/9811127 [math.CO], 1998.
Gus Wiseman, Non-isomorphic representatives of the a(3) = 104 digraphs.
Index entries for sequences related to binary matrices

Cf. A000088, A000273, A001173, A001174, A002416, A003087, A003216, A002724.

NSeq := function ( n ) return Sum(List(ConjugacyClasses(SymmetricGroup(n)), c -> (2^Length(Orbits(Group(Representative(c)), CartesianProduct([1..n],[1..n]), OnTuples))) * Size(c)))/Factorial(n); end; # Dan Hoey, May 04 2001

Join[{1,2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s] /. Table[s[i]->2, {i,1,n^2-n}], {n,2,7}]] (* Geoffrey Critzer, Nov 02 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];
a[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 08 2018, after Andrew Howroyd *)
dinorm[m_]:=If[m=={},{},If[Union@@m!=Range[Max@@Flatten[m]],dinorm[m/.Apply[Rule,Table[{(Union@@m)[[i]],i},{i,Length[Union@@m]}],{1}]],First[Sort[dinorm[m,1]]]]];
dinorm[m_,aft_]:=If[Length[Union@@m]<=aft,{m},With[{mx=Table[Count[m,i,{2}],{i,Select[Union@@m,#1>=aft&]}]},Union@@(dinorm[#1,aft+1]&)/@Union[Table[Map[Sort,m/.{par+aft-1->aft,aft->par+aft-1},{0}],{par,First/@Position[mx,Max[mx]]}]]]];
Table[Length[Union[dinorm/@Subsets[Tuples[Range[n],2]]]],{n,0,3}] (* Gus Wiseman, Jun 17 2019 *)

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, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

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

a(n) = sum {1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...] / (1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 2^sum {i, j>=1} (gcd(i, j)*s_i*s_j). - Christian G. Bower, Jan 05 2004

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

More terms from Vladeta Jovovic, Feb 07 2000

Still more terms from Dan Hoey, May 04 2001

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 0, 1, 4, 76, 4232, 611528, 222688092, 205040866270, 484396550160186, 2987729989350536868, 48933147333828638153224, 2160018687398735805070288200, 260218032038985813416099131315377, 86440094822917159858790627703492969772

Offset: 0

Andrew Howroyd, Jan 01 2022

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Andrew Howroyd, PARI Program, Jan 2022.
R. W. Robinson, Counting digraphs with restrictions on the strong components, Combinatorics and Graph Theory '95 (T.-H. Ku, ed.), World Scientific, Singapore (1995), 343-354.
Wikipedia, Strongly connected component

Row sums of A350750.
The labeled version is A350730.
Cf. A001174, A035512, A086345, A350751.

A350489seq(15) \\ See Links for program code.

A086345 Number of connected oriented graphs (i.e., connected directed graphs with no bidirected edges) on n nodes.

Original entry on oeis.org

1, 1, 1, 5, 34, 535, 20848, 2120098, 572849763, 415361983540, 815590925440865, 4373589784210012634, 64535461714821630421106, 2637732191356603658136444467, 300363258297687600380548275359231

Offset: 0

Eric W. Weisstein, Jul 16 2003

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..50
Musa Demirci, Ugur Ana, and Ismail Naci Cangul, Properties of Characteristic Polynomials of Oriented Graphs, Proc. Int'l Conf. Adv. Math. Comp. (ICAMC 2020) Springer, see p. 61.
Chathura Kankanamge, Multiple Continuous Subgraph Query Optimization Using Delta Subgraph Queries, Master Maths Thesis, Univ. of Waterloo, 2018.
Eric Weisstein's World of Mathematics, Oriented Graph

Cf. A054941 (labeled case), A001174, A281446 (multisets).

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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total @ Quotient[v - 1, 2];
a1174[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
b = Array[a1174, 15];
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
A086345 = EULERi[b] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

from functools import lru_cache
from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
from sympy import mobius, divisors
def A086345(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q-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)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
    return sum(mobius(d)*c(n//d) for d in divisors(n,generator=True))//n if n else 1 # Chai Wah Wu, Jul 15 2024

Inverse Euler transform of A001174. - Andrew Howroyd, Nov 03 2017

More terms from Vladeta Jovovic, Jul 19 2003

a(0)=1 prepended by Andrew Howroyd, Sep 09 2018

A001173 Half the number of binary relations on n unlabeled points.

Original entry on oeis.org

1, 5, 52, 1522, 145984, 48464496, 56141454464, 229148550030864, 3333310786076963968, 174695272746749919580928, 33301710992539090379269318144, 23278728241293494533015563325552128, 60084295633556503802059558812644803074048, 576025077880237078776946730871618386151571214336

Offset: 1

N. J. A. Sloane

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

Chai Wah Wu, Table of n, a(n) for n = 1..59
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
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.

Cf. A000595, A001174.

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[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2 n!)];
Array[a, 12] (* Jean-François Alcover, Aug 01 2019, after Andrew Howroyd in A000595 *)

from itertools import product
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A001173(n): return int(sum(Fraction(1<>1 # Chai Wah Wu, Jul 02 2024

a(n) = A000595(n)/2. - Sean A. Irvine, Mar 16 2012

More terms from Vladeta Jovovic, Apr 18 2000

a(13)-a(14) (based on A000595) from Pontus von Brömssen, Aug 04 2022

A083670 Number of different antisymmetric relations on n unlabeled points.

Original entry on oeis.org

1, 2, 7, 44, 558, 16926, 1319358, 269695440, 146202099255, 212360894456310, 834625722216941739, 8954592469138636320960, 264305834899495393164591240, 21607243912704793462806305720502, 4921054357098031770205099867497197328

Offset: 0

Goetz Pfeiffer (Goetz.Pfeiffer(AT)nuigalway.ie), May 02 2003

Andrew Howroyd, Table of n, a(n) for n = 0..50
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

Cf. A083667 (labeled antisymmetric relations).

Cf. A001174, A101460.

f := function(n) local s, m, c, t, x, a, j; s := 0; m := [1..n]; c := Combinations(m,2); t := Tuples(m,2); for x in ConjugacyClasses(SymmetricGroup(n)) do a := Representative(x); j := Length(Cycles(a,m)); s := s+Size(x)*2^j*3^(Length(Cycles(a,t,OnPairs))-Length(Cycles(a,c,OnSets))-j); od; return s/Factorial(n); end;

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[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]] - 1, 2], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p]*2^Length[p], {p, IntegerPartitions[n]}]; s/n!];
a /@ Range[0, 14] (* Jean-François Alcover, Jan 07 2021, 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, gcd(v[i],v[j]))) + sum(i=1, #v, (v[i]-1)\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)*2^#p); s/n!} \\ Andrew Howroyd, Oct 24 2019

Euler transform of A101460. - Andrew Howroyd, Oct 24 2019

A350733 Triangle read by rows: T(n,k) is the number of oriented graphs on n unlabeled nodes with k arcs, n >= 0, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 4, 10, 12, 10, 4, 1, 1, 4, 13, 41, 78, 131, 144, 107, 50, 12, 1, 1, 4, 14, 55, 187, 539, 1292, 2500, 3817, 4512, 4112, 2740, 1274, 376, 56, 1, 1, 4, 14, 58, 240, 1009, 3643, 11815, 32538, 76145, 149724, 247329, 340364, 387834, 361450, 271177, 159872, 71320, 22690, 4604, 456

Offset: 0

Andrew Howroyd, Jan 13 2022

			Triangle begins:
  [0] 1;
  [1] 1;
  [2] 1, 1;
  [3] 1, 1, 3,  2;
  [4] 1, 1, 4, 10, 12, 10,   4;
  [5] 1, 1, 4, 13, 41, 78, 131, 144, 107, 50, 12;
  ...

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

Row sums are A001174.

Cf. A350734.

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)^g )) * prod(i=1, #v, my(c=v[i]); t(c)^((c-1)\2))}
row(n)={my(s=0); forpart(p=n, s+=permcount(p)*edges(p, i->1+2*x^i)); Vecrev(s/n!)}
{ for(n=0, 6, print(row(n))) }

A350913 Number of oriented graphs on n unlabeled nodes whose underlying graph is regular.

Original entry on oeis.org

1, 1, 2, 3, 10, 17, 244, 2077, 181018, 12150445, 6986854715, 2456586421099, 12983287104044905, 40482495806423235417, 1213455558602787270259889, 29044259315697996254338202296, 6058969047090883735962137093497249, 785177832305082826579135707562767426031

Offset: 0

Andrew Howroyd, Jan 29 2022

nonn

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

The labeled version is A351264.
Row sums of A350912.
Cf. A001174, A005176, A350911.

A126119 Numerators of sequence of fractions with e.g.f. (1+x)/(1-x)^(3/2).

Original entry on oeis.org

1, 5, 27, 195, 1785, 19845, 259875, 3918915, 66891825, 1274998725, 26843892075, 618718975875, 15495473018025, 419010239773125, 12167108660581875, 377607284571391875, 12473420957563190625, 436953531082636693125, 16179945969799083346875, 631461179013117650071875

Offset: 0

N. J. A. Sloane, Mar 22 2007

Denominators are successive powers of 2.

			The fractions are 1, 5/2, 27/4, 195/8, 1785/16, 19845/32, 259875/64, ...

Vincenzo Librandi, Table of n, a(n) for n = 0..200

Cf. A001174, A126115.

CoefficientList[Series[(1+2*x)/(1-2*x)^(3/2), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Feb 25 2014 *)

{a(n)= if(n<0, 0, n!* polcoeff( (1+2*x)/ (1-2*x +x*O(x^n))^(3/2), n))} /* Michael Somos, Apr 08 2007 */

E.g.f.: (1+2*x)/(1-2*x)^(3/2)
From Sergei N. Gladkovskii, Jul 23 2012: (Start)
a(n) = (4*n+1)*((2*n)!)/( n!*(2^n) ).
G.f.: 3*Q(0), where Q(k)= 1 - (2*k+2)/(3*(2*k+1) - 9*x*(2*k+1)^2*(2*k+3)/(3*x*(2*k+1)*(2*k+3) - (2*k+2)/Q(k+1))); (continued fraction, 3rd kind, 3-step).
(End).
a(n) ~ 2^(n+5/2) * n^(n+1) / exp(n). - Vaclav Kotesovec, Feb 25 2014

A000250 Number of symmetric reflexive relations on n nodes: (1/2)*A000666.

Original entry on oeis.org

1, 3, 10, 45, 272, 2548, 39632, 1104306, 56871880, 5463113568, 978181717680, 326167542296048, 202701136710498400, 235284321080559981952, 511531711735594715527360, 2089424601541011618029114896, 16084004145036771186002041099712, 234026948449058790311618594954430848, 6454432593140577452393525511509194184320

Offset: 1

N. J. A. Sloane

Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; Enumeration of graphs with signed points and lines. J. Graph Theory 1 (1977), no. 4, 295-308.
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.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
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).

Jean-François Alcover, Table of n, a(n) for n = 1..40
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]

Cf. A000595, A001173, A001174.

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[Sum[GCD[v[[i]], v[[j]]], {j, 1, i - 1}], {i, 2, Length[v]} ] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/(2  n!)];
a /@ Range[19] (* Jean-François Alcover, Jan 17 2020, after Andrew Howroyd in A000666 *)

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

More terms from Vladeta Jovovic, Apr 18 2000

More terms from Herman Jamke (hermanjamke(AT)fastmail.fm), May 05 2007

cp's OEIS Frontend

A000666 Number of symmetric relations on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A000595 Number of binary relations on n unlabeled points.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Python

Formula

Extensions

A350489 Number of strongly connected oriented graphs on n unlabeled nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A086345 Number of connected oriented graphs (i.e., connected directed graphs with no bidirected edges) on n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A001173 Half the number of binary relations on n unlabeled points.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A083670 Number of different antisymmetric relations on n unlabeled points.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula

A350733 Triangle read by rows: T(n,k) is the number of oriented graphs on n unlabeled nodes with k arcs, n >= 0, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links