A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.

1, 3, 45, 3411, 1809459, 7071729867, 208517974495911, 47481903377454219975, 85161307642554753639601848, 1221965550839348597865127102714827, 142024245093355901785105779901319683262778, 135056692539998733060710198802224149631056479068139

Offset: 0

Author

N. J. A. Sloane

Keywords

• easy
• nonn

Comments

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

Also nonisomorphic relations on 3-state logic.

References

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

Links

• R. W. Robinson and Alois P. Heinz, Table of n, a(n) for n = 0..40 (terms n = 1..13 from R. W. Robinson)
• Frank Harary, Edgar M. Palmer, Robert W. Robinson, Allen J. Schwenk, Enumeration of graphs with signed points and lines, J. Graph Theory 1 (1977), no. 4, 295-308.
• R. W. Robinson, Notes - "A Present for Neil Sloane"
• R. W. Robinson, Notes - computer printout

Crossrefs

Cf. A000595, A001374, A053467, A053516.

Programs

Mathematica

Prepend[Table[CycleIndex[Join[PairGroup[SymmetricGroup[n],Ordered], Permutations[Range[n^2-n+1,n^2]],2],s]/.Table[s[i]->3,{i,1,n^2-n}],{n,2,7}],1] (* Geoffrey Critzer, Oct 20 2012 *)
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[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
a[n_] := (s=0; Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!);
Array[a, 15, 0] (* Jean-François Alcover, Jul 08 2018, 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, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017

Python

from itertools import combinations
from math import prod, gcd, factorial
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A004105(n): return int(sum(Fraction(3**((sum(p[r]*p[s]*gcd(r,s) for r,s in combinations(p.keys(),2))<<1)+sum(q*r**2 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 10 2024

Formula

a(n) = Sum_{1*s_1+2*s_2+...=n} (fixA[s_1, s_2, ...]/ (1^s_1*s_1!*2^s_2*s_2!*...)) where fixA[s_1, s_2, ...] = 3^Sum_{i, j>=1} (gcd(i,j)*s_i*s_j).

Extensions

More terms from Vladeta Jovovic, Jan 14 2000

Formula from Christian G. Bower, Jan 06 2004