0,3

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).

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.

R. W. Robinson, personal communication.

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

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

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 1..22 from R. W. Robinson)

M. Adamaszek, The smallest nonevasive graph property, Disc. Mathem. Graph Theory 34 (2014) 857

Edward A. Bender and E. Rodney Canfield, Enumeration of connected invariant graphs, Journal of Combinatorial Theory, Series B 34.3 (1983): 268-278. See p. 273.

J. Cummings, D. Kral, F. Pfender, K. Sperfeld et al., Monochromatic triangles in three-coloured graphs, arXiv preprint arXiv:1206.1987 [math.CO]. 2012. - From N. J. A. Sloane, Nov 25 2012

Harald Fripertinger, The cycle type of the induced action on 2-subsets

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.

Vladeta Jovovic, Formulae for the number T(n,k) of n-multigraphs on k nodes

R. W. Robinson, Notes - "A Present for Neil Sloane"

R. W. Robinson, Notes - computer printout

R. W. Robinson & N. J. A. Sloane, Correspondence, 1970-1980

Euler transform of A053465. - Andrew Howroyd, Sep 25 2018

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];

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]}];

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

Array[a, 16, 0] (* Jean-François Alcover, Aug 17 2019, after Andrew Howroyd *)

(PARI)

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}

edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}

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

(Python)

from itertools import combinations

from math import prod, gcd, factorial

from fractions import Fraction

from sympy.utilities.iterables import partitions

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

A column of A063841.

Cf. A053465.

Sequence in context: A009400 A217388 A390165 * A072638 A262843 A080526

Adjacent sequences: A004099 A004100 A004101 * A004103 A004104 A004105

nonn,nice,easy

More terms from Vladeta Jovovic, Jan 06 2000

a(0)=1 prepended and a(15) added by Andrew Howroyd, Sep 25 2018

approved