|
%I M1650 N0646 #132 Aug 29 2022 02:21:26
%S 1,2,6,20,90,544,5096,79264,2208612,113743760,10926227136,
%T 1956363435360,652335084592096,405402273420996800,
%U 470568642161119963904,1023063423471189431054720,4178849203082023236058229792,32168008290073542372004082199424
%N Number of symmetric relations on n nodes.
%C Each node may or may not be related to itself.
%C Also the number of rooted graphs on n+1 nodes.
%C The 1-to-1 correspondence is as follows: Given a rooted graph on n+1 nodes, replace each edge joining the root node to another node with 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.
%C Also the number of the graphs with n nodes whereby each node is colored or not colored. A loop can be interpreted as a colored node. - _Juergen Will_, Oct 31 2011
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 101, 241.
%D 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.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H David Applegate, <a href="/A000666/b000666.txt">Table of n, a(n) for n = 0..80</a> [Shortened file because terms grow rapidly: see Applegate link below for additional terms]
%H David Applegate, <a href="/A000666/a000666.txt">Table of n, a(n) for n = 0..100</a>
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
%H R. L. Davis, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0055294-2">The number of structures of finite relations</a>, Proc. Amer. Math. Soc. 4 (1953), 486-495.
%H R. L. Davis, <a href="/A000568/a000568_4.pdf">Structure of dominance relations</a>, Bull. Math. Biophys., 16 (1954), 131-140. [Annotated scanned copy]
%H F. Harary, <a href="http://dx.doi.org/10.1090/S0002-9947-1955-0068198-2">The number of linear, directed, rooted, and connected graphs</a>, Trans. Am. Math. Soc. 78 (1955) 445-463, eq. (24).
%H Frank Harary, Edgar M. Palmer, Robert W. Robinson and Allen J. Schwenk, <a href="http://dx.doi.org/10.1002/jgt.3190010405">Enumeration of graphs with signed points and lines</a>, J. Graph Theory 1 (1977), no. 4, 295-308.
%H Adib Hassan, Po-Chien Chung and Wayne B. Hayes, <a href="https://arxiv.org/abs/1708.04341">Graphettes: Constant-time determination of graphlet and orbit identity including (possibly disconnected) graphlets up to size 8</a>, arXiv:1708.04341 [cs.DS], 2017.
%H Mathematics Stack Exchange, <a href="http://math.stackexchange.com/questions/41386/enumerating-graphs-with-self-loops">Enumerating Graphs with Self-Loops</a>, Jan 23 2014.
%H M. D. McIlroy, <a href="/A000088/a000088.pdf">Calculation of numbers of structures of relations on finite sets</a>, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22. [Annotated scanned copy]
%H W. Oberschelp, <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002298732">Kombinatorische Anzahlbestimmungen in Relationen</a>, Math. Ann., 174 (1967), 53-78.
%H W. Oberschelp, <a href="/A000666/a000666_1.pdf">The number of non-isomorphic m-graphs</a>, Presented at Mathematical Institute Oberwolfach, July 3 1967 [Scanned copy of manuscript]
%H W. Oberschelp, <a href="/A000662/a000662.pdf"> Strukturzahlen in endlichen Relationssystemen</a>, in Contributions to Mathematical Logic (Proceedings 1966 Hanover Colloquium), pp. 199-213, North-Holland Publ., Amsterdam, 1968. [Annotated scanned copy]
%H G. Pfeiffer, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html">Counting Transitive Relations</a>, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
%H Marko Riedel, <a href="/A000666/a000666_2.maple.txt">Maple code for sequence.</a>
%H Marko Riedel et al., <a href="https://math.stackexchange.com/questions/41386/">Enumerating Graphs with Self-Loops</a>
%H R. W. Robinson, <a href="/A000666/a000666_2.pdf">Notes - "A Present for Neil Sloane"</a>
%H R. W. Robinson, <a href="/A004102/a004102_1.pdf">Notes - computer printout</a>
%H Sage, <a href="http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html">Common Graphs (Graph Generators)</a>
%H Lorenzo Sauras-Altuzarra, <a href="/A000666/a000666.png">Graphs</a>
%H J. M. Tangen and N. J. A. Sloane, <a href="/A000666/a000666.pdf">Correspondence, 1976-1976</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RootedGraph.html">Rooted Graph</a>
%F Euler transform of A054921. - _N. J. A. Sloane_, Oct 25 2018
%F 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).
%F 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]
%F 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.
%F a(n) ~ 2^(n*(n+1)/2)/n! [McIlroy, 1955]. - _Vaclav Kotesovec_, Dec 19 2016
%p # see Riedel link above
%t 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 *)
%t Table[Module[{eds,pms,leq},
%t eds=Select[Tuples[Range[n],2],OrderedQ];
%t pms=Map[Sort,eds/.Table[i->Part[#,i],{i,n}]]&/@Permutations[Range[n]];
%t leq=Function[seq,PermutationCycles[Ordering[seq],Length]]/@pms;
%t Total[Thread[Power[2,leq]]]/n!
%t ],{n,0,8}] (* This is after _Geoffrey Critzer_'s program but does not use the (deprecated) Combinatorica package. - _Gus Wiseman_, Jul 21 2016 *)
%t 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];
%t edges[v_] := Sum[Sum[GCD[v[[i]], v[[j]]], {j, 1, i-1}], {i, 2, Length[v]}] + Sum[Quotient[v[[i]], 2] + 1, {i, 1, Length[v]}];
%t a[n_] := a[n] = (s = 0; Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!);
%t Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 17}] (* _Jean-François Alcover_, Nov 13 2017, after _Andrew Howroyd_ *)
%o (PARI)
%o 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}
%o edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2 + 1)}
%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%Y Cf. A000595, A001172, A001174, A006905, A000250, A054921 (connected relations).
%K nonn,nice
%O 0,2
%A _N. J. A. Sloane_
%E Description corrected by _Christian G. Bower_
%E More terms from _Vladeta Jovovic_, Apr 18 2000
%E Entry revised by _N. J. A. Sloane_, Mar 06 2007
|
