A004102 -id:A004102 - 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

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 4, 1, 1, 4, 10, 11, 1, 1, 5, 20, 66, 34, 1, 1, 6, 35, 276, 792, 156, 1, 1, 7, 56, 900, 10688, 25506, 1044, 1, 1, 8, 84, 2451, 90005, 1601952, 2302938, 12346, 1, 1, 9, 120, 5831, 533358, 43571400, 892341888, 591901884, 274668, 1

Offset: 1

N. J. A. Sloane, Aug 25 2001

The first five rows admit the g.f. 1/(1-x), 1/(1-x)^2, 1/(1-x)^4 and those given in A063842, A063843. Is it known that the n-th row admits a rational g.f. with denominator (1-x)^A000124(n)? - M. F. Hasler, Jan 19 2012

T(n+1,k-1) is the number of unoriented ways to color the edges of a regular n-dimensional simplex using up to k colors. - Robert A. Russell, Aug 21 2019

			Table begins
===========================================================
n\k| 0    1       2         3           4             5
---|-------------------------------------------------------
1  | 1    1       1         1           1             1 ...
2  | 1    2       3         4           5             6 ...
3  | 1    4      10        20          35            56 ...
4  | 1   11      66       276         900          2451 ...
5  | 1   34     792     10688       90005        533358 ...
6  | 1  156   25506   1601952    43571400     661452084 ...
7  | 1 1044 2302938 892341888 95277592625 4364646955812 ...
...
T(3,2)=10 because there are 10 unlabeled graphs with 3 nodes with at most 2 edges connecting any pair.
(. . .),(.-. .),(.-.-.),(.-.-.-),(.=. .),(.=.=.),(.=.=.=),(.-.=.),(.-.-.=),(.=.=.-). - _Geoffrey Critzer_, Jan 23 2012

Chai Wah Wu, Table of n, a(n) for n = 1..1584 (terms 1..820 from Andrew Howroyd)
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Columns give A000088, A004102, A053400, A053420, A053421.
Rows (4th and 5th) are listed in A063842, A063843.
Cf. A327084 (unoriented simplex edge colorings).

(* This code gives the array T(n,k). *) Needs["Combinatorica`"]; Transpose[Table[Table[PairGroupIndex[SymmetricGroup[n],s]/.Table[s[i]->k+1, {i,0,Binomial[n,2]}], {n,1,7}], {k,0,6}]]//Grid (* Geoffrey Critzer, Jan 23 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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
T[n_, k_] := (s=0; Do[s += permcount[p]*(k+1)^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Table[T[n-k, k], {n, 1, 10}, {k, n-1, 0, -1}] // Flatten (* 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, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
T(n, k) = {my(s=0); forpart(p=n, s+=permcount(p)*(k+1)^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 A063841_T(n,k): return int(sum(Fraction((k+1)**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>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 09 2024

T(n,k) = A327084(n-1,k+1) for n > 1. - Robert A. Russell, Aug 21 2019

More terms from Vladeta Jovovic, Sep 03 2001

A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.

Original entry on oeis.org

1, 3, 45, 3411, 1809459, 7071729867, 208517974495911, 47481903377454219975, 85161307642554753639601848, 1221965550839348597865127102714827, 142024245093355901785105779901319683262778, 135056692539998733060710198802224149631056479068139

Offset: 0

N. J. A. Sloane

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

Also nonisomorphic relations on 3-state logic.

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson and Alois P. Heinz, Table of n, a(n) for n = 0..40 (terms n = 1..13 from R. W. Robinson)
Frank Harary, Edgar M. Palmer, Robert W. Robinson, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout

Cf. A000595, A001374, A053467, A053516.

Prepend[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s]/.Table[s[i]->3,{i,1,n^2-n}],{n,2,7}],1] (* 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];
a[n_] := (s=0; Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15, 0] (* 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])}
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 A004105(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())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 10 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, ...] = 3^Sum_{i, j>=1} (gcd(i,j)*s_i*s_j).

More terms from Vladeta Jovovic, Jan 14 2000

Formula from Christian G. Bower, Jan 06 2004

A004103 Number of nets on n unlabeled nodes.

Original entry on oeis.org

1, 2, 9, 56, 705, 19548, 1419237, 278474976, 148192635483, 213558945249402, 836556995284293897, 8962975658381123937708, 264404516190234685662666051, 21610417954162750247842392794292, 4921335335427778307286708119839406529, 3138313838161414849743136458064895837170596

Offset: 0

N. J. A. Sloane

nonn

A net in this context is a graph with both signed vertices and signed edges. - Andrew Howroyd, Sep 25 2018

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..22 from R. W. Robinson)
Frank Harary, Edgar M. Palmer, Robert W. Robinson, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout

Cf. A004102 (signed edges only), A000666 (signed vertices only).

Cf. A004107.

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], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p]*2^Length[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 16, 0] (* Jean-François Alcover, Aug 17 2019, 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)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)*2^#p); s/n!} \\ Andrew Howroyd, Sep 25 2018

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A004103(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)*r+(q*r*(r-1)>>1) for q, r in p.items()))<Chai Wah Wu, Jul 09 2024

a(0)=1 prepended and a(13)-a(14) added by Andrew Howroyd, Sep 25 2018

A004104 Number of self-dual signed graphs with n nodes. Also number of self-complementary 2-multigraphs on n nodes.

Original entry on oeis.org

1, 1, 2, 6, 20, 86, 662, 8120, 171526, 5909259, 348089533, 33883250874, 5476590066777, 1490141905609371, 666003784522738152, 509204473666338077658, 636051958071749028811326, 1375164117171886868027357906, 4844133410739656724629165903483, 29777568550007746192195431057341474

Offset: 1

N. J. A. Sloane

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

Of a(1) through a(22) only a(3) = 2 is prime. - Jonathan Vos Post, Feb 19 2011

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50 (terms 1..22 from R. W. Robinson)
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. 273.
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.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout

Cf. A004102, A052111, A052112, A052113.

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[If[Mod[v[[i]]*v[[j]], 2] == 0, GCD[v[[i]], v[[j]]], 0], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[If[Mod[v[[i]], 2] == 0, Quotient[v[[i]], 4]*2, 0], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 1, 25}] (* Jean-François Alcover, Feb 27 2019, 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, if(v[i]*v[j]%2==0, gcd(v[i],v[j])))) + sum(i=1, #v, if(v[i]%2==0, v[i]\4*2))}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Sep 16 2018

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A004104(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2) if not (r&1 and s&1))+sum(((q>>1)&-2)*r+(q*r*(r-1)>>1) for q, r in p.items() if q&1^1)),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # Chai Wah Wu, Jul 09 2024

More terms from Vladeta Jovovic, Jan 19 2000

a(18)-a(20) added by Andrew Howroyd, Sep 16 2018

A053400 Number of 3-multigraphs on n nodes.

Original entry on oeis.org

1, 4, 20, 276, 10688, 1601952, 892341888, 1799786093088, 13042490003160192, 341378170022783017472, 32526326484972756063585792, 11367103329997359707194173746176, 14669222110846093400698801891700529152

Offset: 1

Vladeta Jovovic, Jan 06 2000

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

Andrew Howroyd, Table of n, a(n) for n = 1..50
Harald Fripertinger, The cycle type of the induced action on 2-subsets
Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

Column k=3 of A063841.

Cf. A004102.

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A053400(n): return int(sum(Fraction(1<<(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>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 09 2024

A053465 Number of connected 2-multigraphs on n nodes.

Original entry on oeis.org

1, 1, 2, 7, 53, 712, 24576, 2275616, 589543159, 420188096140, 819411181635025, 4381819315336997184, 64583749250393921183423, 2638507778912832094660037006, 300397569392490080058575760090548, 95776592061550107555640978862165082446

Offset: 0

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

Also the number of connected signed graphs on n unlabeled nodes. - Andrew Howroyd, Sep 25 2018

Andrew Howroyd, Table of n, a(n) for n = 0..50
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. 273.

Cf. A004102, A318590.

A004102 = Import["https://oeis.org/A004102/b004102.txt", "Table"][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
Join[{1}, EulerInvTransform[A004102 // Rest]] (* Jean-François Alcover, Sep 12 2019, after Andrew Howroyd, updated Mar 17 2020 *)

Inverse Euler transform of A004102. - Andrew Howroyd, Sep 25 2018

a(0)=1 prepended and terms a(15) and beyond from Andrew Howroyd, Sep 25 2018

A053588 Number of self-complementary 4-multigraphs on n nodes.

Original entry on oeis.org

1, 1, 3, 16, 121, 1480, 50993, 3279685, 505641590, 152461906778, 103587671805408, 145528904385412088, 442626996609870050404, 2918362542591139744394993, 40446812392580562094804791143, 1260273961234324967695235253182680, 80686628450087709982052029871655471264

Offset: 1

Vladeta Jovovic, Jan 19 2000

nonn

V. Jovovic, On the number of m-place relations (in Russian), Logiko-algebraicheskie konstruktsii, Tver, 1992, 59-66.
J. Xu, Ch. R. Wang, J. F. Wang, The theory of self-complementary k-multigraphs (in Chinese), Pure Appl. Math. [Chuncui Shuxue yu Yingyong Shuxue] 10 (1994), Special Issue, 18-22.

Andrew Howroyd, Table of n, a(n) for n = 1..50
D. Wille, Enumeration of self-complementary structures, J. Comb. Theory B 25 (1978) 143-150.

Cf. A004102, A004104, A053420.

permcount[v_] := Module[{m = 1, s = 0, t, i, k = 0}, 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[If[EvenQ[v[[i]]*v[[j]]], GCD[v[[i]], v[[j]]], 0], {i, 2, Length[v]}, {j, 1, i - 1}] + Sum[If[EvenQ[v[[i]]], 2 Quotient[v[[i]], 4], 0], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*5^edges[p], {p, IntegerPartitions[n]}]; s/n!];
a /@ Range[1, 20] (* Jean-François Alcover, Sep 22 2019, 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, if(v[i]*v[j]%2==0, gcd(v[i], v[j])))) + sum(i=1, #v, if(v[i]%2==0, v[i]\4*2))}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*5^edges(p)); s/n!} \\ Andrew Howroyd, Sep 17 2018

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

A004106 Number of line-self-dual nets (or edge-self-dual nets) with n nodes.

Original entry on oeis.org

1, 2, 3, 8, 29, 148, 1043, 11984, 229027, 6997682, 366204347, 30394774084, 4363985982959, 994090870519508, 393850452332173999, 249278602955869472540, 275042591834324901085904, 488860279973733024992540668, 1514493725905920009795681408275

Offset: 0

N. J. A. Sloane

nonn

A net in this context is a graph with both signed vertices and signed edges. A net is line-self-dual if changing the signs on all edges leaves the graph unchanged up to isomorphism. - Andrew Howroyd, Sep 25 2018

F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.
R. W. Robinson, personal communication.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..22 from R. W. Robinson)
Frank Harary, Edgar M. Palmer, Robert W. Robinson, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
R. W. Robinson, Notes - "A Present for Neil Sloane"
R. W. Robinson, Notes - computer printout

Cf. A004103, A004104, A004105, A004107, A320490.

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[If[Mod[v[[i]] v[[j]], 2] == 0, GCD[v[[i]], v[[j]]], 0], {j, 1, i - 1}], {i, 2, Length[v]}] + Sum[If[Mod[v[[i]], 2] == 0, 2 Quotient[v[[i]], 4], 0], {i, 1, Length[v]}];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p]*2^Length[p], {p, IntegerPartitions[n]}]; s/n!];
Array[a, 19, 0] (* Jean-François Alcover, Aug 17 2019, 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, if(v[i]*v[j]%2==0, gcd(v[i], v[j])))) + sum(i=1, #v, if(v[i]%2==0, v[i]\4*2))}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)*2^#p); s/n!} \\ Andrew Howroyd, Sep 25 2018

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A004106(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2) if not (r&1 and s&1))+sum(((q>>1)&-2)*r+(q*r*(r-1)>>1) for q, r in p.items() if q&1^1))<Chai Wah Wu, Jul 10 2024

a(0)=1 prepended and a(17)-a(18) added by Andrew Howroyd, Sep 25 2018

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

A063841 Table T(n,k) giving number of k-multigraphs on n nodes (n >= 1, k >= 0) read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A004103 Number of nets on n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A004104 Number of self-dual signed graphs with n nodes. Also number of self-complementary 2-multigraphs on n nodes.

Views

Author

Keywords

Comments

References

Links