|
|
A004105
|
|
Number of point-self-dual nets with 2n nodes. Also number of directed 2-multigraphs with loops on n nodes.
(Formerly M3153)
|
|
8
|
|
|
1, 3, 45, 3411, 1809459, 7071729867, 208517974495911, 47481903377454219975, 85161307642554753639601848, 1221965550839348597865127102714827, 142024245093355901785105779901319683262778, 135056692539998733060710198802224149631056479068139
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
|
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).
|
|
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!);
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|