login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000595 Relations: number of nonisomorphic unlabeled binary relations on n labeled nodes.
(Formerly M1980 N0784)
21
1, 2, 10, 104, 3044, 291968, 96928992, 112282908928, 458297100061728, 6666621572153927936, 349390545493499839161856, 66603421985078180758538636288, 46557456482586989066031126651104256, 120168591267113007604119117625289606148096, 1152050155760474157553893461743236772303142428672 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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

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

Charles R. Greathouse IV, Table of n, a(n) for n = 0..37

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

A. Casagrande, C. Piazza, A. Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Preprint 2015.

R. 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, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.

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. 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, 2013

Marko Riedel, Counting nonisomorphic binary relations (includes Maple code).

J. M. Tangen and N. J. A. Sloane, Correspondence, 1976-1976

L. Travis, [math/9811127] Graphical Enumeration: A Species-Theoretic Approach

Index entries for sequences related to binary matrices

FORMULA

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

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

PROG

(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

CROSSREFS

Cf. A001173, A001174.

Sequence in context: A154256 A005799 A208730 * A087234 A049538 A217901

Adjacent sequences:  A000592 A000593 A000594 * A000596 A000597 A000598

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Feb 07 2000

Still more terms from Dan Hoey, May 04 2001

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified May 30 18:26 EDT 2016. Contains 273520 sequences.