login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of signed graphs with n nodes. Also number of 2-multigraphs on n nodes.
(Formerly M2874)
20

%I M2874 #61 Jul 09 2024 19:14:19

%S 1,1,3,10,66,792,25506,2302938,591901884,420784762014,819833163057369,

%T 4382639993148435207,64588133532185722290294,

%U 2638572375815762804156666529,300400208094064113266621946833097,95776892467035669509813163910815022152

%N Number of signed graphs with n nodes. Also number of 2-multigraphs on n nodes.

%C A 2-multigraph is similar to an ordinary graph except there are 0, 1 or 2 edges between any two nodes (self-loops are not allowed).

%D F. Harary and R. W. Robinson, Exposition of the enumeration of point-line-signed graphs, pp. 19 - 33 of Proc. Second Caribbean Conference Combinatorics and Computing (Bridgetown, 1977). Ed. R. C. Read and C. C. Cadogan. University of the West Indies, Cave Hill Campus, Barbados, 1977. vii+223 pp.

%D R. W. Robinson, personal communication.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A004102/b004102.txt">Table of n, a(n) for n = 0..50</a> (terms 1..22 from R. W. Robinson)

%H M. Adamaszek, <a href="https://doi.org/10.7151/dmgt.1766">The smallest nonevasive graph property</a>, Disc. Mathem. Graph Theory 34 (2014) 857

%H Edward A. Bender and E. Rodney Canfield, <a href="https://doi.org/10.1016/0095-8956(83)90040-0">Enumeration of connected invariant graphs</a>, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.

%H J. Cummings, D. Kral, F. Pfender, K. Sperfeld et al., <a href="http://arxiv.org/abs/1206.1987">Monochromatic triangles in three-coloured graphs</a>, arXiv preprint arXiv:1206.1987 [math.CO]. 2012. - From _N. J. A. Sloane_, Nov 25 2012

%H Harald Fripertinger, <a href="http://www.mathe2.uni-bayreuth.de/frib/html/book/hyl00_42.html">The cycle type of the induced action on 2-subsets</a>

%H Harary, Frank; Palmer, Edgar M.; Robinson, Robert W.; Schwenk, Allen J.; <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 Vladeta Jovovic, <a href="/A063843/a063843.rtf">Formulae for the number T(n,k) of n-multigraphs on k nodes</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 R. W. Robinson & N. J. A. Sloane, <a href="/A004102/a004102.pdf">Correspondence, 1970-1980</a>

%F Euler transform of A053465. - _Andrew Howroyd_, Sep 25 2018

%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], {i, 1, Length[v]}];

%t a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];

%t Array[a, 16, 0] (* _Jean-François Alcover_, Aug 17 2019, 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)}

%o a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ _Andrew Howroyd_, Sep 25 2018

%o (Python)

%o from itertools import combinations

%o from math import prod, gcd, factorial

%o from fractions import Fraction

%o from sympy.utilities.iterables import partitions

%o def A004102(n): return int(sum(Fraction(3**(sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))+sum((q>>1)*r+(q*r*(r-1)>>1) for q, r in p.items())),prod(q**r*factorial(r) for q, r in p.items())) for p in partitions(n))) # _Chai Wah Wu_, Jul 09 2024

%Y A column of A063841.

%Y Cf. A053465.

%K nonn,nice,easy

%O 0,3

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Jan 06 2000

%E a(0)=1 prepended and a(15) added by _Andrew Howroyd_, Sep 25 2018