cp's OEIS Frontend

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

%I A004102 M2874 #61 Jul 09 2024 19:14:19
%S A004102 1,1,3,10,66,792,25506,2302938,591901884,420784762014,819833163057369,
%T A004102 4382639993148435207,64588133532185722290294,
%U A004102 2638572375815762804156666529,300400208094064113266621946833097,95776892467035669509813163910815022152
%N A004102 Number of signed graphs with n nodes. Also number of 2-multigraphs on n nodes.
%C A004102 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 A004102 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 A004102 R. W. Robinson, personal communication.
%D A004102 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%D A004102 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A004102 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 A004102 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 A004102 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 A004102 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 A004102 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 A004102 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 A004102 Vladeta Jovovic, <a href="/A063843/a063843.rtf">Formulae for the number T(n,k) of n-multigraphs on k nodes</a>
%H A004102 R. W. Robinson, <a href="/A000666/a000666_2.pdf">Notes - "A Present for Neil Sloane"</a>
%H A004102 R. W. Robinson, <a href="/A004102/a004102_1.pdf">Notes - computer printout</a>
%H A004102 R. W. Robinson & N. J. A. Sloane, <a href="/A004102/a004102.pdf">Correspondence, 1970-1980</a>
%F A004102 Euler transform of A053465. - _Andrew Howroyd_, Sep 25 2018
%t A004102 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 A004102 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 A004102 a[n_] := Module[{s = 0}, Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!];
%t A004102 Array[a, 16, 0] (* _Jean-François Alcover_, Aug 17 2019, after _Andrew Howroyd_ *)
%o A004102 (PARI)
%o A004102 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 A004102 edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
%o A004102 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ _Andrew Howroyd_, Sep 25 2018
%o A004102 (Python)
%o A004102 from itertools import combinations
%o A004102 from math import prod, gcd, factorial
%o A004102 from fractions import Fraction
%o A004102 from sympy.utilities.iterables import partitions
%o A004102 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 A004102 A column of A063841.
%Y A004102 Cf. A053465.
%K A004102 nonn,nice,easy
%O A004102 0,3
%A A004102 _N. J. A. Sloane_
%E A004102 More terms from _Vladeta Jovovic_, Jan 06 2000
%E A004102 a(0)=1 prepended and a(15) added by _Andrew Howroyd_, Sep 25 2018