cp's OEIS Frontend

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

%I A004105 M3153 #55 Jul 10 2024 15:03:07
%S A004105 1,3,45,3411,1809459,7071729867,208517974495911,47481903377454219975,
%T A004105 85161307642554753639601848,1221965550839348597865127102714827,
%U A004105 142024245093355901785105779901319683262778,135056692539998733060710198802224149631056479068139
%N A004105 Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.
%C A004105 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).
%C A004105 Also nonisomorphic relations on 3-state logic.
%D A004105 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 A004105 R. W. Robinson, personal communication.
%D A004105 R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
%D A004105 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A004105 R. W. Robinson and Alois P. Heinz, <a href="/A004105/b004105.txt">Table of n, a(n) for n = 0..40</a> (terms n = 1..13 from R. W. Robinson)
%H A004105 Frank Harary, Edgar M. Palmer, Robert W. Robinson, 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 A004105 R. W. Robinson, <a href="/A000666/a000666_2.pdf">Notes - "A Present for Neil Sloane"</a>
%H A004105 R. W. Robinson, <a href="/A004102/a004102_1.pdf">Notes - computer printout</a>
%F A004105 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).
%t A004105 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 *)
%t A004105 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 A004105 edges[v_] := Sum[2*GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[v];
%t A004105 a[n_] := (s=0; Do[s += permcount[p]*3^edges[p], {p, IntegerPartitions[n]}]; s/n!);
%t A004105 Array[a, 15, 0] (* _Jean-François Alcover_, Jul 08 2018, after _Andrew Howroyd_ *)
%o A004105 (PARI)
%o A004105 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 A004105 edges(v) = {sum(i=2, #v, sum(j=1, i-1, 2*gcd(v[i],v[j]))) + sum(i=1, #v, v[i])}
%o A004105 a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*3^edges(p)); s/n!} \\ _Andrew Howroyd_, Oct 22 2017
%o A004105 (Python)
%o A004105 from itertools import combinations
%o A004105 from math import prod, gcd, factorial
%o A004105 from fractions import Fraction
%o A004105 from sympy.utilities.iterables import partitions
%o A004105 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
%Y A004105 Cf. A000595, A001374, A053467, A053516.
%K A004105 easy,nonn
%O A004105 0,2
%A A004105 _N. J. A. Sloane_
%E A004105 More terms from _Vladeta Jovovic_, Jan 14 2000
%E A004105 Formula from _Christian G. Bower_, Jan 06 2004