|
| |
|
|
A000666
|
|
Number of symmetric relations on n nodes.
(Formerly M1650 N0646)
|
|
8
|
|
|
|
1, 2, 6, 20, 90, 544, 5096, 79264, 2208612, 113743760, 10926227136, 1956363435360, 652335084592096, 405402273420996800, 470568642161119963904, 1023063423471189431054720
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Each node may or may not be related to itself.
Also the number of rooted graphs on n+1 nodes.
The 1-1-correspondence is as follows. Given a rooted graph on n+1 nodes, replace each edge joining the root node to another node by a self-loop at that node and erase the root node. The result is an undirected graph on n nodes which is the graph of the symmetric relation.
Also the number of the graphs with n nodes whereby each node is coloured or not coloured. A loop can be interpreted as a coloured node. - Juergen Will, Oct 31 2011
|
|
|
REFERENCES
|
R. L. Davis, The numbers of structures of finite relations, Proc. Amer. Math. Soc., 4 (1953), 486-494.
F. Harary, The number of linear, directed, rooted and connected graphs, Trans. Amer. Math. Soc., 78 (1955), 445-463.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 101, 241.
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.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
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
|
David Applegate, Table of n, a(n) for n = 0..80 [Shortened file because terms grow rapidly: see Applegate link below for additional terms]
David Applegate, Table of n, a(n) for n = 0..100
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.
Eric Weisstein's World of Mathematics, Rooted Graph
|
|
|
FORMULA
|
Let G_{n+1,k} be the number of rooted graphs on n+1 nodes with k edges and let G_{n+1}(x) = Sum_{k=0..n(n+1)/2} G_{n+1,k} x^k. Thus a(n) = G_{n+1}(1). Let S_n(x_1, ..., x_n) denote the cycle index for Sym_n. (cf. the link in A000142).
Compute x_1*S_n and regard it as the cycle index of a set of permutations on n+1 points and find the corresponding cycle index for the action on the n(n+1)/2 edges joining those points (the corresponding "pair group"). Finally, by replacing each x_i by 1+x^i gives G_{n+1}(x). [Harary]
Example, n=2. S_2 = (1/2)*(x_1^2+x_2), x_1*S_2 = (1/2)*(x_1^3+x_1*x_2). The pair group is (1/2)*(x_1^2+x_1*x_2) and so G_3(x) = (1/2)*((1+x)^3+(1+x)*(1+x^2)) = 1+2*x+2*x^2+x^3; set x=1 to get a(2) = 6.
|
|
|
MATHEMATICA
|
Join[{1, 2}, Table[CycleIndex[Join[PairGroup[SymmetricGroup[n]], Permutations[Range[n*(n-1)/2+1, n*(n+1)/2]], 2], s] /. Table[s[i]->2, {i, 1, n^2-n}], {n, 2, 8}]] (* Geoffrey Critzer, Nov 04 2011 *)
|
|
|
CROSSREFS
|
Cf. A000595, A001172, A001174, A006905, A000250.
Sequence in context: A004104 A079468 A124382 * A180890 A027321 A027315
Adjacent sequences: A000663 A000664 A000665 * A000667 A000668 A000669
|
|
|
KEYWORD
|
nonn,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Description corrected by Christian G. Bower. More terms from Vladeta Jovovic, Apr 18 2000
Entry revised by N. J. A. Sloane, Mar 06 2007
|
|
|
STATUS
|
approved
|
| |
|
|
