|
| |
|
|
A000595
|
|
Number of nonisomorphic unlabeled binary relations on n 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)
R. L. Davis, The number of structures of finite relations, Proc. Amer. Math. Soc. 4 (1953), 486-495.
Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; 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, Sept. 15, 1955, pp. 14-22.
W. Oberschelp, Kombinatorische Anzahlbestimmungen in Relationen, Math. Ann., 174 (1967), 53-78.
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.
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
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 2 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;
|
|
|
CROSSREFS
|
Cf. A001173, A001174.
Sequence in context: A154256 A005799 A208730 * A087234 A049538 A217901
Adjacent sequences: A000592 A000593 A000594 * A000596 A000597 A000598
|
|
|
KEYWORD
|
nonn,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms from Vladeta Jovovic, Feb 07 2000. Still more terms and GAP program from Dan Hoey (Hoey(AT)aic.nrl.navy.mil), May 04 2001
|
|
|
STATUS
|
approved
|
| |
|
|
