cp's OEIS Frontend

A000719 Number of disconnected graphs with n nodes.

%I A000719 M1452 N0574 #54 Feb 16 2025 08:32:21
%S A000719 0,0,1,2,5,13,44,191,1229,13588,288597,12297299,1031342116,
%T A000719 166123498733,50668194387427,29104827043066808,31455591302381718651,
%U A000719 64032471448906164191208,245999896712611657677614268,1787823725136869060356731751124
%N A000719 Number of disconnected graphs with n nodes.
%C A000719 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
%D A000719 R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
%D A000719 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000719 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000719 Alois P. Heinz, <a href="/A000719/b000719.txt">Table of n, a(n) for n = 0..87</a> (first 31 terms from David Wasserman)
%H A000719 R. K. Guy, <a href="/A005347/a005347.pdf">The Second Strong Law of Small Numbers</a>, Math. Mag, 63 (1990), no. 1, 3-20. [Annotated scanned copy]
%H A000719 F. Harary, <a href="http://dx.doi.org/10.1090/S0002-9947-1955-0068198-2">The number of linear, directed, rooted, and connected graphs</a>, Trans. Amer. Math. Soc. 78 (1955), 445-463.
%H A000719 M. L. Stein and P. R. Stein, <a href="http://dx.doi.org/10.2172/4180737">Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points</a>. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
%H A000719 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DisconnectedGraph.html">Disconnected Graph.</a>
%H A000719 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-ConnectedGraph.html">k-Connected Graph.</a>
%H A000719 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/k-Edge-ConnectedGraph.html">k-Edge-Connected Graph.</a>
%t A000719 << "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 *)
%o A000719 (Python)
%o A000719 from functools import lru_cache
%o A000719 from itertools import combinations
%o A000719 from fractions import Fraction
%o A000719 from math import prod, gcd, factorial
%o A000719 from sympy import mobius, divisors
%o A000719 from sympy.utilities.iterables import partitions
%o A000719 def A000719(n):
%o A000719     if n == 0: return 0
%o A000719     @lru_cache(maxsize=None)
%o A000719     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)))
%o A000719     @lru_cache(maxsize=None)
%o A000719     def c(n): return n*b(n)-sum(c(k)*b(n-k) for k in range(1,n))
%o A000719     return b(n)-sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # _Chai Wah Wu_, Jul 03 2024
%Y A000719 Equals (A000088) minus (A001349).
%K A000719 nonn,easy,nice
%O A000719 0,4
%A A000719 _N. J. A. Sloane_
%E A000719 More terms from _Christian G. Bower_
%E A000719 Further terms from _Vladeta Jovovic_, Apr 14 2000