A054915 Number of unlabeled connected graphs with n nodes such that complement is also connected.

1, 0, 0, 1, 8, 68, 662, 9888, 247492, 11427974, 994403266, 163028488360, 50169784370486, 28952819268460634, 31368276315718175152, 63938104521922794457626, 245807799210635120355337360, 1787085725352186477232522962312, 24634233605674730786262294027930520

Offset

1,5

Links

Andrew Howroyd, Table of n, a(n) for n = 1..50

V. A. Liskovets, Some easily derivable sequences, J. Integer Sequences, 3 (2000), #00.2.2.

Formula

a(n) = 2*A001349(n) - A000088(n).

Mathematica

nn = 15; Clear[g, c, a, b]; c[z_] := Sum[a[n] z^n, {n, 1, nn}];
g[z_] := Sum[NumberOfGraphs[n] z^n, {n, 0, nn}]; sol =
SolveAlways[ 0 == Series[g[z] - Product[1/(1 - z^i)^a[i], {i, 1, nn}], {z, 0, nn}], z]; 2*(Flatten[Table[a[n], {n, 1, nn}] /. sol]) - (Drop[
CoefficientList[Series[g[z], {z, 0, nn + 1}], z], 1]) (* Geoffrey Critzer, Aug 12 2016 *)

Prog

(Python)
from functools import lru_cache
from itertools import combinations
from fractions import Fraction
from math import prod, gcd, factorial
from sympy import mobius, divisors
from sympy.utilities.iterables import partitions
def A054915(n):
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<<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)))
    @lru_cache(maxsize=None)
    def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1, n))
    return (sum(mobius(n//d)*c(d) for d in divisors(n, generator=True))//n<<1)-b(n) # Chai Wah Wu, Jul 03 2024

Crossrefs

Cf. A000088, A001349.

Sequence in context: A068766 A233736 A279266 * A073555 A167859 A243246

Adjacent sequences: A054912 A054913 A054914 * A054916 A054917 A054918

Keyword

nonn,easy

Author

N. J. A. Sloane, May 23 2000

Extensions

More terms from Vladeta Jovovic, Jul 17 2000

Status

approved