A000595 Number of binary relations on n unlabeled points.
1, 2, 10, 104, 3044, 291968, 96928992, 112282908928, 458297100061728, 6666621572153927936, 349390545493499839161856, 66603421985078180758538636288, 46557456482586989066031126651104256, 120168591267113007604119117625289606148096, 1152050155760474157553893461743236772303142428672
Offset: 0
Examples
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)
References
- 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).
Links
- 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
Programs
-
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
-
Mathematica
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 *) -
PARI
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 -
Python
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<
Formula
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
Extensions
More terms from Vladeta Jovovic, Feb 07 2000
Still more terms from Dan Hoey, May 04 2001
Comments