cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-5 of 5 results.

A001349 Number of simple connected graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The singleton graph K_1 is considered connected even though it is conventionally taken to have vertex connectivity 0. - Eric W. Weisstein, Jul 21 2020
Inverse Euler transform of A000088 but with a(0) omitted so that Sum_{k>=0} A000088(n) * x^n = Product_{k>0} (1 - x^k)^-a(k). It is debatable if there is a connected graph with 0 nodes and so a(0)=0 or better start from a(1)=1. - Michael Somos, Jun 01 2013. [As Harary once remarked in a famous paper ("Is the null-graph a pointless concept?"), the empty graph has every property, which is why a(0)=1. - N. J. A. Sloane, Apr 08 2014]

Examples

			G.f. = 1 + x + x^2 + 2*x^3 + 6*x^4 + 21*x^5 + 112*x^6 + 853*x^7 + ....

References

  • P. Butler and R. W. Robinson, On the computer calculation of the number of nonseparable graphs, pp. 191 - 208 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.
  • F. Harary and R. C. Read, Is the null-graph a pointless concept?, pp. 37-44 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, page 48, c(x). Also page 242.
  • Lupanov, O. B. Asymptotic estimates of the number of graphs with n edges. (Russian) Dokl. Akad. Nauk SSSR 126 1959 498--500. MR0109796 (22 #681).
  • Lupanov, O. B. "On asymptotic estimates of the number of graphs and networks with n edges." Problems of Cybernetics [in Russian], Moscow 4 (1960): 5-21.
  • R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
  • R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1978.
  • 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).
  • Robin J. Wilson, Introduction to Graph Theory, Academic Press, 1972. (But see A126060!)

Links

Crossrefs

Cf. A000088, A002218, A006290, A000719, A201922 (Multiset transform).
Row sums of A054924.

Programs

  • Maple
    # To produce all connected graphs on 4 nodes, for example (from N. J. A. Sloane, Oct 07 2013):
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency, restrictto=connected):
  • Mathematica
    <<"Combinatorica`"; max = 19; A000088 = Table[ NumberOfGraphs[n], {n, 0, max}]; f[x_] = 1 - Product[ 1/(1 - x^k)^a[k], {k, 1, max}]; a[0] = a[1] = a[2] = 1; coes = CoefficientList[ Series[ f[x], {x, 0, max}], x]; sol = First[ Solve[ Thread[ Rest[ coes + A000088 ] == 0]]]; Table[ a[n], {n, 0, max}] /. sol (* Jean-François Alcover, Nov 24 2011 *)
terms = 20;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Join[{1}, EULERi[Array[a88, terms]]] (* Jean-François Alcover, Jul 28 2018, after Andrew Howroyd *)
  • 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 A001349(n):
    if n == 0: return 1
    @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 sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n # Chai Wah Wu, Jul 02-03 2024
  • Sage
    property=lambda G: G.is_connected()
def a(n):
    return len([1 for G in graphs(n) if property(G)])
# Ralf Stephan, May 30 2014

Formula

For asymptotics see Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014

Extensions

More terms from Ronald C. Read

A274934 Number of unlabeled graphs with n nodes that have two components, neither of which is the empty graph.

Original entry on oeis.org

0, 0, 1, 1, 3, 8, 30, 145, 1028, 12320, 274806, 12007355, 1019030239, 165091859656, 50502058492266, 29054157815353374, 31426486309136279775, 64001015806929213894372, 245935864212056913811759534, 1787577725208700551275529005084
Offset: 0

Views

Author

R. J. Mathar and N. J. A. Sloane, Jul 18 2016

Keywords

Examples

			a(6) = A216785(6)+2 =30 where the two additional graphs have two equal components (of which there are A001349(3)=2 choices).

Links

Crossrefs

Cf. A001349, A216785 (non-isomorphic components), A275165, A275166, column 2 of A201922.

Programs

  • Mathematica
    terms = 20;
mob[m_, n_] := If[Mod[m, n] == 0, MoebiusMu[m/n], 0];
EULERi[b_] := Module[{a, c, i, d}, c = {}; For[i = 1, i <= Length[b], i++, c = Append[c, i*b[[i]] - Sum[c[[d]]*b[[i - d]], {d, 1, i - 1}]]]; a = {}; For[i = 1, i <= Length[b], i++, a = Append[a, (1/i)*Sum[mob[i, d]*c[[d]], {d, 1, i}]]]; Return[a]];
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[GCD[v[[i]], v[[j]]], {i, 2, Length[v]}, {j, 1, i - 1}] + Total[Quotient[v, 2]];
a88[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
A[x_] = Join[{1}, EULERi[Array[a88, terms]]].x^Range[0, terms] - 1;
CoefficientList[(A[x]^2 + A[x^2])/2 + O[x]^terms, x] (* Jean-François Alcover, Sep 28 2018, after Andrew Howroyd in A001349 *)

Formula

G.f.: [A(x)^2 + A(x^2)]/2 where A(x) is the o.g.f. for A001349 without the initial constant 1.
a(n) = A201922(n,2). - R. J. Mathar, Jul 20 2016

A106240 Triangle read by rows: T(n,m) = number of unlabeled cographs on n nodes with m connected components.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 12, 7, 3, 1, 1, 33, 20, 8, 3, 1, 1, 90, 55, 22, 8, 3, 1, 1, 261, 162, 63, 23, 8, 3, 1, 1, 766, 477, 188, 65, 23, 8, 3, 1, 1, 2312, 1450, 564, 196, 66, 23, 8, 3, 1, 1, 7068, 4446, 1732, 590, 198, 66, 23, 8, 3, 1, 1, 21965, 13858, 5384, 1824, 598, 199, 66, 23, 8, 3, 1, 1
Offset: 1

Views

Author

Washington Bomfim, May 06 2005

Keywords

Examples

			T(10,8) = 3 because the partitions of 10 with 8 parts are 31111111 and 22111111. The partition 31111111 corresponds to 2 graphs and the partition 22111111 corresponds to only one.
T(n,m) = 1, if and only if m>=n-1. Because A000669(1)=A000669(2)=1, the partitions of n with all parts <=2 correspond to summands = 1. If there is only a summand (or partition), the total is equal to 1. It is clear that for m>=n-1 there is only one partition of n with exactly m parts.
Triangle begins:
   1,
   1,  1,
   2,  1,  1,
   5,  3,  1, 1,
  12,  7,  3, 1, 1,
  33, 20,  8, 3, 1, 1,
  90, 55, 22, 8, 3, 1, 1,

Links

Crossrefs

Cf. A000669 (first column), A000084 (row sums), A201922.

Formula

T(n, m) = sum over the partitions of n with m parts: 1K1 + 2K2 + ... + nKn = n, K1 + K2 + ... + Kn = m, of Product_{i=1..n} binomial(A000669(i)+Ki-1, Ki).

A201968 Limiting number of graphs with m+n nodes and m connected components as m tends to infinity.

Original entry on oeis.org

1, 1, 3, 9, 33, 157, 1077, 12562, 276361, 12023304, 1019341931, 165104554019, 50503104222056, 29054325051128443, 31426537149908636858, 64001044963441537716700, 245935895697060179316310623, 1787577789272803153324620542087, 24637809499317378365431171138790458
Offset: 0

Views

Author

Max Alekseyev, Dec 07 2011

Keywords

Formula

Limit of A201922(m+n,m) as m tends to infinity.
a(n) = A201922(2*n,n) = A201922(2*n+1,n+1) = ...
a(n) = sum over the partitions of n of Product_{i=1..n} binomial(A001349(i+1)+Ki-1, Ki), where Ki is the number of parts equal to i, 1*K1 + 2*K2 + ... + n*Kn = n.

A224031 Number of connected components over all simple unlabeled graphs with n nodes.

Original entry on oeis.org

0, 1, 3, 7, 19, 55, 222, 1303, 13845, 289796, 12309107, 1031600490, 166135132131, 50669199124597, 29104991031790932, 31455641633255556350, 64032500451659605651790, 245999928109779646497947269, 1787823789106309664923287885113
Offset: 0

Views

Author

Geoffrey Critzer, Mar 30 2013

Keywords

Links

Programs

  • Mathematica
    nn=15; f[list_] := Total[Table[list[[i]]*(i-1), {i,1,Length[list]}]]; g[x_]:=Sum[NumberOfGraphs[n]x^n,{n,0,nn}]; c[x_]:=Sum[a[n]x^n,{n,0,nn}]; a[0]=1; sol=SolveAlways[g[x]==Normal[Series[Product[1/(1-x^i)^a[i], {i,1,nn}], {x,0,nn}]], x]; b=Drop[Flatten[Table[a[n],{n,0,nn}]/.sol],1]; Map[f,CoefficientList[Series[Product[1/(1-y x^i)^b[[i]], {i,1,nn}], {x,0,nn}], {x,y}]]

Formula

Sum_{m=1..n} A201922(m,n).
Showing 1-5 of 5 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.