A000719 Number of disconnected graphs with n nodes.

0, 0, 1, 2, 5, 13, 44, 191, 1229, 13588, 288597, 12297299, 1031342116, 166123498733, 50668194387427, 29104827043066808, 31455591302381718651, 64032471448906164191208, 245999896712611657677614268, 1787823725136869060356731751124

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

a(n) is also the number of simple unlabeled graphs on n+1 nodes with diameter 2 and connectivity 1. - Geoffrey Critzer, Oct 23 2016

References

• R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..87 (first 31 terms from David Wasserman)
• R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
• F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463.
• M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
• Eric Weisstein's World of Mathematics, Disconnected Graph.
• Eric Weisstein's World of Mathematics, k-Connected Graph.
• Eric Weisstein's World of Mathematics, k-Edge-Connected Graph.

Crossrefs

Equals (A000088) minus (A001349).

Programs

Mathematica

<< "Combinatorica`"; max = 18; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^b[k], {k, 1, max}]; b[0] = b[1] = b[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; a[n_] := a[n] = A000088[[n+1]] - b[n] /. sol; a[0] = a[1] = 0; Table[a[n], {n, 0, max}] (* Jean-François Alcover, Nov 24 2011 *)

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 A000719(n):
    if n == 0: return 0
    @lru_cache(maxsize=None)
    def b(n): return int(sum(Fraction(1<>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 b(n)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 03 2024

Extensions

More terms from Christian G. Bower

Further terms from Vladeta Jovovic, Apr 14 2000