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-10 of 56 results. Next

A000088 Number of simple graphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 2, 4, 11, 34, 156, 1044, 12346, 274668, 12005168, 1018997864, 165091172592, 50502031367952, 29054155657235488, 31426485969804308768, 64001015704527557894928, 245935864153532932683719776, 1787577725145611700547878190848, 24637809253125004524383007491432768
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler transform of the sequence A001349.
Also, number of equivalence classes of sign patterns of totally nonzero symmetric n X n matrices.

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 430.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
  • F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
  • Thomas Boyer-Kassem, Conor Mayo-Wilson, Scientific Collaboration and Collective Knowledge: New Essays, New York, Oxford University Press, 2018, see page 47.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 54.
  • 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).
  • M. D. McIlroy, Calculation of numbers of structures of relations on finite sets, Massachusetts Institute of Technology, Research Laboratory of Electronics, Quarterly Progress Reports, No. 17, Sep. 15, 1955, pp. 14-22.
  • 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, 1976.
  • 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

Crossrefs

Partial sums of A002494.
Cf. A000666 (graphs with loops), A001349 (connected graphs), A002218, A006290, A003083.
Column k=1 of A063841.
Column k=2 of A309858.
Row sums of A008406.
Cf. also A000055, A000664.
Partial sums are A006897.

Programs

  • Maple
    # To produce all graphs on 4 nodes, for example:
with(GraphTheory):
L:=[NonIsomorphicGraphs](4,output=graphs,outputform=adjacency): # N. J. A. Sloane, Oct 07 2013
seq(GraphTheory[NonIsomorphicGraphs](n,output=count),n=1..10); # Juergen Will, Jan 02 2018
# alternative Maple program:
b:= proc(n, i, l) `if`(n=0 or i=1, 1/n!*2^((p-> add(ceil((p[j]-1)/2)
      +add(igcd(p[k], p[j]), k=1..j-1), j=1..nops(p)))([l[], 1$n])),
       add(b(n-i*j, i-1, [l[], i$j])/j!/i^j, j=0..n/i))
    end:
a:= n-> b(n$2, []):
seq(a(n), n=0..20);  # Alois P. Heinz, Aug 14 2019
  • Mathematica
    Needs["Combinatorica`"]
Table[NumberOfGraphs[n], {n, 0, 19}] (* Geoffrey Critzer, Mar 12 2011 *)
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]];
a[n_] := Module[{s = 0}, Do[s += permcount[p]*2^edges[p], {p, IntegerPartitions[n]}]; s/n!];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
b[n_, i_, l_] := If[n==0 || i==1, 1/n!*2^(Function[p, Sum[Ceiling[(p[[j]]-1 )/2]+Sum[GCD[p[[k]], p[[j]]], {k, 1, j-1}], {j, 1, Length[p]}]][Join[l, Table[1, {n}]]]), Sum[b[n-i*j, i-1, Join[l, Table[i, {j}]]]/j!/i^j, {j, 0, n/i}]];
a[n_] := b[n, n, {}];
a /@ Range[0, 20] (* Jean-François Alcover, Dec 03 2019, after Alois P. Heinz *)
  • 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, gcd(v[i],v[j]))) + sum(i=1, #v, v[i]\2)}
a(n) = {my(s=0); forpart(p=n, s+=permcount(p)*2^edges(p)); s/n!} \\ Andrew Howroyd, Oct 22 2017
  • Python
    from itertools import combinations
from math import prod, factorial, gcd
from fractions import Fraction
from sympy.utilities.iterables import partitions
def A000088(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))) # Chai Wah Wu, Jul 02 2024
  • Sage
    def a(n):
    return len(list(graphs(n)))
# Ralf Stephan, May 30 2014

Formula

a(n) = 2^binomial(n, 2)/n!*(1+(n^2-n)/2^(n-1)+8*n!/(n-4)!*(3*n-7)*(3*n-9)/2^(2*n)+O(n^5/2^(5*n/2))) (see Harary, Palmer reference). - Vladeta Jovovic and Benoit Cloitre, Feb 01 2003
a(n) = 2^binomial(n, 2)/n!*[1+2*n$2*2^{-n}+8/3*n$3*(3n-7)*2^{-2n}+64/3*n$4*(4n^2-34n+75)*2^{-3n}+O(n^8*2^{-4*n})] where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1). - Keith Briggs, Oct 24 2005
From David Pasino (davepasino(AT)yahoo.com), Jan 31 2009: (Start)
a(n) = a(n, 2), where a(n, t) is the number of t-uniform hypergraphs on n unlabeled nodes (cf. A000665 for t = 3 and A051240 for t = 4).
a(n, t) = Sum_{c : 1*c_1+2*c_2+...+n*c_n=n} per(c)*2^f(c), where:
..per(c) = 1/(Product_{i=1..n} c_i!*i^c_i);
..f(c) = (1/ord(c)) * Sum_{r=1..ord(c)} Sum_{x : 1*x_1+2*x_2+...+t*x_t=t} Product_{k=1..t} binomial(y(r, k; c), x_k);
..ord(c) = lcm{i : c_i>0};
..y(r, k; c) = Sum_{s|r : gcd(k, r/s)=1} s*c_(k*s) is the number of k-cycles of the r-th power of a permutation of type c. (End)
a(n) ~ 2^binomial(n,2)/n! [see Flajolet and Sedgewick p. 106, Gross and Yellen, p. 519, etc.]. - N. J. A. Sloane, Nov 11 2013
For asymptotics see also Lupanov 1959, 1960, also Turner and Kautz, p. 18. - N. J. A. Sloane, Apr 08 2014
a(n) = G(1) where G(z) = (1/n!) Sum_g det(I-g z^2)/det(I-g z) and g runs through the natural matrix n X n representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - Leonid Bedratyuk, May 02 2015
From Keith Briggs, Jun 24 2016: (Start)
a(n) = 2^binomial(n,2)/n!*(
1+
2^( -n + 1)*n$2+
2^(-2*n + 3)*n$3*(n-7/3)+
2^(-3*n + 6)*n$4*(4*n^2/3 - 34*n/3 + 25) +
2^(-4*n + 10)*n$5*(8*n^3/3 - 142*n^2/3 + 2528*n/9 - 24914/45) +
2^(-5*n + 15)*n$6*(128*n^4/15 - 2296*n^3/9 + 25604*n^2/9 - 630554*n/45 + 25704) +
2^(-6*n + 21)*n$7*(2048*n^5/45 - 18416*n^4/9 + 329288*n^3/9 - 131680816*n^2/405 + 193822388*n/135 - 7143499196/2835) + ...),
where n$k is the falling factorial: n$k = n(n-1)(n-2)...(n-k+1), using the method of Wright 1969.
(End)
a(n) = 1/n*Sum_{k=1..n} a(n-k)*A003083(k). - Andrey Zabolotskiy, Aug 11 2020

Extensions

Harary gives an incorrect value for a(8); compare A007149

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

A013922 Number of labeled connected graphs with n nodes and 0 cutpoints (blocks or nonseparable graphs).

Original entry on oeis.org

0, 1, 1, 10, 238, 11368, 1014888, 166537616, 50680432112, 29107809374336, 32093527159296128, 68846607723033232640, 290126947098532533378816, 2417684612523425600721132544, 40013522702538780900803893881856
Offset: 1

Views

Author

Stanley Selkow (sms(AT)owl.WPI.EDU)

Keywords

Comments

Or, number of labeled 2-connected graphs with n nodes.

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p.402.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 9.
  • R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.20(b), g(n).

Links

Crossrefs

Cf. A002218, A004115, A095983.
Row sums of triangle A123534.

Programs

  • Mathematica
    seq[n_] := CoefficientList[Log[x/InverseSeries[x*D[Log[Sum[2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^n], x]]], x]*Range[0, n-2]!;
seq[16] (* Jean-François Alcover, Aug 19 2019, after Andrew Howroyd *)
  • PARI
    seq(n)={Vec(serlaplace(log(x/serreverse(x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))))), -n)} \\ Andrew Howroyd, Sep 26 2018

Formula

Harary and Palmer give e.g.f. in Eqn. (1.3.3) on page 10.

A259862 Triangle read by rows: T(n,k) = number of unlabeled graphs with n nodes and connectivity exactly k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 5, 3, 2, 1, 13, 11, 7, 2, 1, 44, 56, 39, 13, 3, 1, 191, 385, 332, 111, 21, 3, 1, 1229, 3994, 4735, 2004, 345, 34, 4, 1, 13588, 67014, 113176, 66410, 13429, 992, 54, 4, 1, 288597, 1973029, 4629463, 3902344, 1109105, 99419, 3124, 81, 5, 1, 12297299, 105731474, 327695586, 388624106, 162318088, 21500415, 820956, 9813, 121, 5, 1
Offset: 1

Views

Author

N. J. A. Sloane, Jul 08 2015

Keywords

Comments

These are vertex-connectivities. Spanning edge-connectivity is A263296. Non-spanning edge-connectivity is A327236. Cut-connectivity is A327127. - Gus Wiseman, Sep 03 2019

Examples

			Triangle begins:
       1;
       1,       1;
       2,       1,       1;
       5,       3,       2,       1;
      13,      11,       7,       2,       1;
      44,      56,      39,      13,       3,     1;
     191,     385,     332,     111,      21,     3,    1;
    1229,    3994,    4735,    2004,     345,    34,    4,  1;
   13588,   67014,  113176,   66410,   13429,   992,   54,  4, 1;
  288597, 1973029, 4629463, 3902344, 1109105, 99419, 3124, 81, 5, 1;
  12297299,105731474,327695586,388624106,162318088,21500415,820956,9813,121,5,1;
  ...

Links

Crossrefs

Columns k=0..10 (up to initial nonzero terms) are A000719, A052442, A052443, A052444, A052445, A324234, A324235, A324088, A324089, A324090, A324091.
Row sums are A000088.
Number of graphs with connectivity at least k for k=1..10 are A001349, A002218, A006290, A086216, A086217, A324240, A324092, A324093, A324094, A324095.
The labeled version is A327334.
Cf. A002494, A263296, A322389, A326786, A327127, A327236.

A095983 Number of 2-edge-connected labeled graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 1, 10, 253, 11968, 1047613, 169181040, 51017714393, 29180467201536, 32121680070545657, 68867078000231169536, 290155435185687263172693, 2417761175748567327193407488, 40013922635723692336670167608181, 1318910073755307133701940625759574016
Offset: 0

Views

Author

Yifei Chen (yifei(AT)mit.edu), Jul 17 2004

Keywords

Comments

From Falk Hüffner, Jun 28 2018: (Start)
Essentially the same sequence arises as the number of connected bridgeless labeled graphs (graphs that are k-edge connected for k >= 2, starting elements of this sequence are 1, 1, 0, 1, 10, 253, 11968, ...).
Labeled version of A007146. (End)
The spanning edge-connectivity of a graph is the minimum number of edges that must be removed (without removing incident vertices) to obtain a graph that is disconnected or covers fewer vertices. This sequence counts graphs with spanning edge-connectivity >= 2, which, for n > 1, are connected graphs with no bridges. - Gus Wiseman, Sep 20 2019

Links

Crossrefs

Cf. A053549, A198046.
The unlabeled version is A007146.
Row sums of A327069 if the first two columns are removed.
BII-numbers of set-systems with spanning edge-connectivity >= 2 are A327109.
Graphs with spanning edge-connectivity 2 are A327146.
Graphs with non-spanning edge-connectivity >= 2 are A327200.
2-vertex-connected graphs are A013922.
Graphs without endpoints are A059167.
Graphs with spanning edge-connectivity 1 are A327071.
Cf. A001187, A002218, A052446, A059166, A100743, A322395, A327079, A327144.

Programs

  • Mathematica
    seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[ Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n+1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k-1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
seq[16] (* Jean-François Alcover, Aug 13 2019, after Andrew Howroyd *)
csm[s_]:=With[{c=Select[Subsets[Range[Length[s]],{2}],Length[Intersection@@s[[#]]]>0&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
spanEdgeConn[vts_,eds_]:=Length[eds]-Max@@Length/@Select[Subsets[eds],Union@@#!=vts||Length[csm[#]]!=1&];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],spanEdgeConn[Range[n],#]>=2&]],{n,0,5}] (* Gus Wiseman, Sep 20 2019 *)
  • PARI
    \\ here p is initially A053549, q is A198046 as e.g.f.s.
seq(n)={my(v=vector(n));
my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))));
my(q=x*exp(p)); p-=q;
for(k=3, n, my(c=polcoeff(p,k)); v[k]=c*(k-1)!; p-=c*q^k);
concat([0],v)} \\ Andrew Howroyd, Jun 18 2018
  • PARI
    seq(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))/x-1), -(n+1))} \\ Andrew Howroyd, Dec 28 2020

Formula

a(n) = A001187(n) - A327071(n). - Gus Wiseman, Sep 20 2019

Extensions

Name corrected and more terms from Pavel Irzhavski, Nov 01 2014
Offset corrected by Falk Hüffner, Jun 17 2018
a(12)-a(16) from Andrew Howroyd, Jun 18 2018

A006290 Number of 3-connected graphs with n nodes.

Original entry on oeis.org

1, 3, 17, 136, 2388, 80890, 5114079, 573273505, 113095167034, 39582550575765, 24908445793058442, 28560405143495819079, 60364410130177223014724, 237403933018799958309530349, 1750323137355778190158082029500, 24333358813699371350715221107464003, 640811613278752754485012443963579501421
Offset: 4

Views

Author

N. J. A. Sloane

Keywords

Comments

Robinson and Walsh list first 25 terms.

References

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

Links

Crossrefs

Row sums of A339072.
Cf. A000088, A001349, A002218, A006289, A007112, A338511.

Extensions

More terms from Ronald C. Read.

A317672 Regular triangle where T(n,k) is the number of clutters (connected antichains) on n + 1 vertices with k maximal blobs (2-connected components).

Original entry on oeis.org

1, 2, 3, 44, 24, 16, 4983, 940, 300, 125, 7565342, 154770, 18000, 4320, 1296, 2414249587694, 318926314, 3927105, 363580, 72030, 16807, 56130437054842366160898, 135200580256336, 10244647168, 99187200, 8028160, 1376256, 262144
Offset: 1

Views

Author

Gus Wiseman, Aug 03 2018

Keywords

Examples

			Triangle begins:
        1
        2       3
       44      24      16
     4983     940     300     125
  7565342  154770   18000    4320    1296

Links

Crossrefs

Row sums are A048143. First column is A275307. Last column is A030019.
Cf. A000272, A001187, A002218, A013922, A134954, A293510, A317631, A317632, A317634, A317635, A317671.

Programs

  • Mathematica
    blg={0,1,2,44,4983,7565342,2414249587694,56130437054842366160898} (* A275307 *);
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Sum[n^(k-1)*Product[blg[[Length[s]+1]],{s,spn}],{spn,Select[sps[Range[n-1]],Length[#]==k&]}],{n,Length[blg]},{k,n-1}]

A326751 BII-numbers of blobs.

Original entry on oeis.org

0, 1, 2, 4, 8, 16, 32, 52, 64, 128, 256, 512, 772, 816, 820, 832, 1024, 1072, 1088, 2048, 2320, 2340, 2356, 2368, 2580, 2592, 2612, 2624, 2836, 2852, 2864, 2868, 2880, 3088, 3104, 3120, 3136, 4096, 4132, 4160, 4612, 4640, 4644, 4672, 5120, 5152, 5184, 8192
Offset: 1

Views

Author

Gus Wiseman, Jul 23 2019

Keywords

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every finite set of finite nonempty sets has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18.
Elements of a set-system are sometimes called edges. In an antichain, no edge is a subset or superset of any other edge. In a 2-vertex-connected set-system, at least two vertices must be removed to make the set-system disconnected. A blob is a connected, 2-vertex-connected antichain of finite, nonempty sets, or, equivalently, a 2-vertex-connected clutter.

Examples

			The sequence of all blobs together with their BII-numbers begins:
     0: {}
     1: {{1}}
     2: {{2}}
     4: {{1,2}}
     8: {{3}}
    16: {{1,3}}
    32: {{2,3}}
    52: {{1,2},{1,3},{2,3}}
    64: {{1,2,3}}
   128: {{4}}
   256: {{1,4}}
   512: {{2,4}}
   772: {{1,2},{1,4},{2,4}}
   816: {{1,3},{2,3},{1,4},{2,4}}
   820: {{1,2},{1,3},{2,3},{1,4},{2,4}}
   832: {{1,2,3},{1,4},{2,4}}
  1024: {{1,2,4}}
  1072: {{1,3},{2,3},{1,2,4}}
  1088: {{1,2,3},{1,2,4}}
  2048: {{3,4}}
  2320: {{1,3},{1,4},{3,4}}
  2340: {{1,2},{2,3},{1,4},{3,4}}
  2356: {{1,2},{1,3},{2,3},{1,4},{3,4}}

Links

Crossrefs

Cf. A000120, A002218, A013922 (2-vertex-connected graphs), A030019, A048143 (clutters), A048793, A070939, A095983, A275307 (spanning blobs), A304118, A304887, A322117, A322397 (2-edge-connected clutters), A326031.
Other BII-numbers: A309314 (hyperforests), A326701 (set partitions), A326703 (chains), A326704 (antichains), A326749 (connected), A326750 (clutters), A326752 (hypertrees), A326754 (covers).

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
tvcQ[eds_]:=And@@Table[Length[csm[DeleteCases[eds,i,{2}]]]<=1,{i,Union@@eds}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Select[Range[0,1000],stableQ[bpe/@bpe[#],SubsetQ]&&Length[csm[bpe/@bpe[#]]]<=1&&tvcQ[bpe/@bpe[#]]&]

A052443 Number of simple unlabeled n-node graphs of connectivity 2.

Original entry on oeis.org

0, 0, 1, 2, 7, 39, 332, 4735, 113176, 4629463, 327695586, 40525166511, 8850388574939, 3453378695335727, 2435485662537561705, 3137225298932374490227, 7448146273273417700880931, 32837456713651735794742705141, 270528237651574516777595556494978, 4186091025846007046878947026003803389
Offset: 1

Views

Author

Eric W. Weisstein

Keywords

Links

Crossrefs

Column k=2 of A259862.
Cf. A000719, A002218, A006290, A052442, A052444, A052445.
The labeled version is A327198.
2-vertex-connected graphs are A013922.
Cf. A322387, A327051, A327101, A327334.

Programs

Formula

a(n) = A002218(n) - A006290(n) for n > 2. - Andrew Howroyd, Sep 04 2019

Extensions

Name clarified and a(8)-a(11) by Jens M. Schmidt, Feb 18 2019
a(2)-a(3) corrected by Andrew Howroyd, Aug 28 2019
a(12)-a(20) from Andrew Howroyd, Sep 04 2019

A327082 BII-numbers of set-systems with cut-connectivity 2.

Original entry on oeis.org

4, 5, 6, 7, 16, 17, 24, 25, 32, 34, 40, 42, 256, 257, 384, 385, 512, 514, 640, 642, 816, 817, 818, 819, 820, 821, 822, 823, 824, 825, 826, 827, 828, 829, 830, 831, 832, 833, 834, 835, 836, 837, 838, 839, 840, 841, 842, 843, 844, 845, 846, 847, 848, 849, 850
Offset: 1

Views

Author

Gus Wiseman, Aug 20 2019

Keywords

Comments

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793. We define the set-system with BII-number n to be obtained by taking the binary indices of each binary index of n. Every set-system (finite set of finite nonempty sets) has a different BII-number. For example, 18 has reversed binary expansion (0,1,0,0,1), and since the binary indices of 2 and 5 are {2} and {1,3} respectively, the BII-number of {{2},{1,3}} is 18. Elements of a set-system are sometimes called edges.
We define the cut-connectivity (A326786, A327237), of a set-system to be the minimum number of vertices that must be removed (along with any resulting empty edges) to obtain a disconnected or empty set-system, with the exception that a set-system with one vertex and no edges has cut-connectivity 1. Except for cointersecting set-systems (A326853, A327039), this is the same as vertex-connectivity (A327334, A327051).

Examples

			The sequence of all set-systems with cut-connectivity 2 together with their BII-numbers begins:
    4: {{1,2}}
    5: {{1},{1,2}}
    6: {{2},{1,2}}
    7: {{1},{2},{1,2}}
   16: {{1,3}}
   17: {{1},{1,3}}
   24: {{3},{1,3}}
   25: {{1},{3},{1,3}}
   32: {{2,3}}
   34: {{2},{2,3}}
   40: {{3},{2,3}}
   42: {{2},{3},{2,3}}
  256: {{1,4}}
  257: {{1},{1,4}}
  384: {{4},{1,4}}
  385: {{1},{4},{1,4}}
  512: {{2,4}}
  514: {{2},{2,4}}
  640: {{4},{2,4}}
  642: {{2},{4},{2,4}}
The first term involving an edge of size 3 is 832: {{1,2,3},{1,4},{2,4}}.

Crossrefs

Positions of 2's in A326786.
BII-numbers for non-spanning edge-connectivity 2 are A327097.
BII-numbers for spanning edge-connectivity 2 are A327108.
The cut-connectivity 1 version is A327098.
The cut-connectivity > 1 version is A327101.
Covering 2-cut-connected set-systems are counted by A327112.
Covering set-systems with cut-connectivity 2 are counted by A327113.
Cf. A000120, A002218, A013922, A048793, A259862, A322387, A322388, A326031, A327041, A327114.

Programs

  • Mathematica
    bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
vertConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Min@@Length/@Select[Subsets[Union@@sys],Function[del,Length[csm[DeleteCases[DeleteCases[sys,Alternatives@@del,{2}],{}]]]!=1]]];
Select[Range[0,100],vertConnSys[bpe/@bpe[#]]==2&]
Showing 1-10 of 56 results. Next

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

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