cp's OEIS Frontend

A000595 Number of binary relations on n unlabeled points.

%I A000595 M1980 N0784 #141 May 15 2025 00:44:18
%S A000595 1,2,10,104,3044,291968,96928992,112282908928,458297100061728,
%T A000595 6666621572153927936,349390545493499839161856,
%U A000595 66603421985078180758538636288,46557456482586989066031126651104256,120168591267113007604119117625289606148096,1152050155760474157553893461743236772303142428672
%N A000595 Number of binary relations on n unlabeled points.
%C A000595 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)).
%C A000595 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
%D A000595 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 76 (2.2.30)
%D A000595 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.
%D A000595 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000595 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000595 Jean-François Alcover, <a href="/A000595/b000595.txt">Table of n, a(n) for n = 0..50</a> (a(0)-a(37) from Charles R. Greathouse IV)
%H A000595 Edward A. Bender and E. Rodney Canfield, <a href="https://doi.org/10.1016/0095-8956(83)90040-0">Enumeration of connected invariant graphs</a>, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 274.
%H A000595 Peter J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H A000595 Alberto Casagrande, Carla Piazza, and Alberto Policriti, <a href="http://sets2015.cnam.fr/papers/00010001.pdf">Is hyper-extensionality preservable under deletions of graph elements?</a>, Preprint 2015.
%H A000595 Alexander Clow, Alfie Davies, and Neil Anderson McKay, <a href="https://arxiv.org/abs/2505.06206">Constructing All Birthday 3 Games as Digraphs</a>, arXiv:2505.06206 [math.CO], 2025. See p. 13.
%H A000595 Matthew Dabkowski, N. Fan, and R. Breiger, <a href="https://doi.org/10.1016/j.socnet.2016.05.005">Exploratory blockmodeling for one-mode, unsigned, deterministic networks using integer programming and structural equivalence</a>, Social Networks, Volume 47, October 2016, Pages 93-106.
%H A000595 Robert L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.
%H A000595 Thomas M. A. Fink, Emmanuel Barillot, and Sebastian E. Ahnert, <a href="https://web.archive.org/web/20210427075631/http://www.tcm.phy.cam.ac.uk/~tmf20/PUBLICATIONS/dynamics_motifs.pdf">Dynamics of network motifs</a>, 2006.
%H A000595 Frank Harary, Edgar M. Palmer, Robert W. Robinson, and Allen J. Schwenk, <a href="http://dx.doi.org/10.1002/jgt.3190010405">Enumeration of graphs with signed points and lines</a>, J. Graph Theory 1 (1977), no. 4, 295-308.
%H A000595 Sergiy Kozerenko, <a href="https://www.researchgate.net/publication/321155460_On_the_abstract_properties_of_Markov_graphs_for_maps_on_trees">On the abstract properties of Markov graphs for maps on trees</a>, Mathematical Bilten 41:2 (2017), pp. 5-21.
%H A000595 M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
%H A000595 W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.
%H A000595 Götz Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%H A000595 Samuel Reid, <a href="http://arxiv.org/abs/1305.0064">On Generalizing a Temporal Formalism for Game Theory to the Asymptotic Combinatorics of S5 Modal Frames</a>, arXiv preprint arXiv:1305.0064 [math.LO], 2013.
%H A000595 Marko Riedel, <a href="http://math.stackexchange.com/questions/356995/counting-non-isomorphic-relations">Counting nonisomorphic binary relations (includes Maple code).</a>
%H A000595 R. W. Robinson, <a href="/A000666/a000666_2.pdf">Notes - "A Present for Neil Sloane"</a>
%H A000595 R. W. Robinson, <a href="/A004102/a004102_1.pdf">Notes - computer printout</a>
%H A000595 J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>
%H A000595 Leopold Travis, <a href="https://arxiv.org/abs/math/9811127">Graphical Enumeration: A Species-Theoretic Approach</a>, arXiv:math/9811127 [math.CO], 1998.
%H A000595 Gus Wiseman, <a href="/A000595/a000595.png">Non-isomorphic representatives of the a(3) = 104 digraphs</a>.
%H A000595 <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>
%F A000595 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
%F A000595 a(n) ~ 2^(n^2)/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016
%e A000595 From _Gus Wiseman_, Jun 17 2019: (Start)
%e A000595 Non-isomorphic representatives of the a(2) = 10 relations:
%e A000595   {}
%e A000595   {1->1}
%e A000595   {1->2}
%e A000595   {1->1, 1->2}
%e A000595   {1->1, 2->1}
%e A000595   {1->1, 2->2}
%e A000595   {1->2, 2->1}
%e A000595   {1->1, 1->2, 2->1}
%e A000595   {1->1, 1->2, 2->2}
%e A000595   {1->1, 1->2, 2->1, 2->2}
%e A000595 (End)
%t A000595 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 *)
%t A000595 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];
%t A000595 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
%t A000595 a[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
%t A000595 Table[a[n], {n, 0, 15}] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%t A000595 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]]]]];
%t A000595 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]]}]]]];
%t A000595 Table[Length[Union[dinorm/@Subsets[Tuples[Range[n],2]]]],{n,0,3}] (* _Gus Wiseman_, Jun 17 2019 *)
%o A000595 (GAP) 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
%o A000595 (PARI)
%o A000595 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}
%o A000595 edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
%o A000595 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o A000595 (Python)
%o A000595 from itertools import product
%o A000595 from math import prod, factorial, gcd
%o A000595 from fractions import Fraction
%o A000595 from sympy.utilities.iterables import partitions
%o A000595 def A000595(n): return int(sum(Fraction(1<<sum(p[r]*p[s]*gcd(r,s) for r,s in product(p.keys(),repeat=2)),prod(q**p[q]*factorial(p[q]) for q in p)) for p in partitions(n))) # _Chai Wah Wu_, Jul 02 2024
%Y A000595 Cf. A000088, A000273, A001173, A001174, A002416, A003087, A003216, A002724.
%K A000595 nonn,nice
%O A000595 0,2
%A A000595 _N. J. A. Sloane_
%E A000595 More terms from _Vladeta Jovovic_, Feb 07 2000
%E A000595 Still more terms from _Dan Hoey_, May 04 2001