login
Number of binary relations on n unlabeled points.
(Formerly M1980 N0784)
45

%I M1980 N0784 #137 Jul 02 2024 12:33:19

%S 1,2,10,104,3044,291968,96928992,112282908928,458297100061728,

%T 6666621572153927936,349390545493499839161856,

%U 66603421985078180758538636288,46557456482586989066031126651104256,120168591267113007604119117625289606148096,1152050155760474157553893461743236772303142428672

%N Number of binary relations on n unlabeled points.

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

%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 P. 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 A. Casagrande, C. Piazza, and A. Policriti, <a href="http://sets2015.cnam.fr/papers/00010001.pdf">Is hyper-extensionality preservable under deletions of graph elements?</a>, Preprint 2015.

%H 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 R. 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 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 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 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 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 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 G. 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 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 Marko Riedel, <a href="http://math.stackexchange.com/questions/356995/counting-non-isomorphic-relations">Counting nonisomorphic binary relations (includes Maple code).</a>

%H R. W. Robinson, <a href="/A000666/a000666_2.pdf">Notes - "A Present for Neil Sloane"</a>

%H R. W. Robinson, <a href="/A004102/a004102_1.pdf">Notes - computer printout</a>

%H J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>

%H L. Travis, <a href="https://arxiv.org/abs/math/9811127">Graphical Enumeration: A Species-Theoretic Approach</a>, arXiv:math/9811127 [math.CO], 1998.

%H Gus Wiseman, <a href="/A000595/a000595.png">Non-isomorphic representatives of the a(3) = 104 digraphs</a>.

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F 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 a(n) ~ 2^(n^2)/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016

%e From _Gus Wiseman_, Jun 17 2019: (Start)

%e Non-isomorphic representatives of the a(2) = 10 relations:

%e {}

%e {1->1}

%e {1->2}

%e {1->1, 1->2}

%e {1->1, 2->1}

%e {1->1, 2->2}

%e {1->2, 2->1}

%e {1->1, 1->2, 2->1}

%e {1->1, 1->2, 2->2}

%e {1->1, 1->2, 2->1, 2->2}

%e (End)

%t 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 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 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];

%t a[n_] := (s=0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);

%t Table[a[n], {n, 0, 15}] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)

%t 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 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 Table[Length[Union[dinorm/@Subsets[Tuples[Range[n],2]]]],{n,0,3}] (* _Gus Wiseman_, Jun 17 2019 *)

%o (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 (PARI)

%o 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 edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}

%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017

%o (Python)

%o from itertools import product

%o from math import prod, factorial, gcd

%o from fractions import Fraction

%o from sympy.utilities.iterables import partitions

%o 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 Cf. A000088, A000273, A001173, A001174, A002416, A003087, A003216, A002724.

%K nonn,nice

%O 0,2

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Feb 07 2000

%E Still more terms from _Dan Hoey_, May 04 2001