0,2

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.

R. L. Davies, 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.

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

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.

Cf. A000595, A001172, A001174, A006905, A000250.

Sequence in context: A004104 A079468 A124382 this_sequence A027321 A027315 A005965

Adjacent sequences: A000663 A000664 A000665 this_sequence A000667 A000668 A000669

nonn,nice

njas

Description corrected by Christian Bower (bowerc(AT)usa.net). More terms from Vladeta Jovovic (vladeta(AT)Eunet.yu), Apr 18 2000

Entry revised by njas, Mar 06 2007