This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000595 Relations: number of nonisomorphic unlabeled binary relations on n labeled nodes.
(Formerly M1980 N0784)

%I M1980 N0784

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

%T 6666621572153927936,349390545493499839161856,

%U 66603421985078180758538636288,46557456482586989066031126651104256,120168591267113007604119117625289606148096,1152050155760474157553893461743236772303142428672

%N Relations: number of nonisomorphic unlabeled binary relations on n labeled nodes.

%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 Charles R. Greathouse IV, <a href="/A000595/b000595.txt">Table of n, a(n) for n = 0..37</a>

%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, 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, 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="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, 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 <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} (fix A[s_1, s_2, ...] / (1^s_1*s_1!*2^s_2*s_2!*...)) where fix A[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

%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_ *)

%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

%Y Cf. A000273, A001173, A001174.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 20 08:50 EDT 2018. Contains 313914 sequences. (Running on oeis4.)