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.

A327148 Irregular triangle read by rows with trailing zeros removed where T(n,k) is the number of labeled simple graphs with n vertices and non-spanning edge-connectivity k.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 4, 18, 27, 14, 1, 56, 250, 402, 240, 65, 10, 1, 1031, 5475, 11277, 9620, 4282, 921, 146, 15, 1
Offset: 0

Views

Author

Gus Wiseman, Aug 27 2019

Keywords

Comments

The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed (along with any isolated vertices) to obtain a disconnected or empty graph.

Examples

			Triangle begins:
   1
   1
   1   1
   1   3   3   1
   4  18  27  14   1
  56 250 402 240  65  10   1
		

Crossrefs

Row sums are A006125.
Column k = 0 is A327199.
Column k = 1 is A327231.
The corresponding triangle for vertex-connectivity is A327125.
The corresponding triangle for spanning edge-connectivity is A327069.
The covering version is A327149.
The unlabeled version is A327236, with covering version A327201.

Programs

  • Mathematica
    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]]]]]]]]];
    edgeConnSys[sys_]:=If[Length[csm[sys]]!=1,0,Length[sys]-Max@@Length/@Select[Union[Subsets[sys]],Length[csm[#]]!=1&]];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],edgeConnSys[#]==k&]],{n,0,4},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

Formula

T(n,k) = Sum_{m = 0..n} binomial(n,m) A327149(m,k). In words, column k is the binomial transform of column k of A327149.

Extensions

a(20)-a(28) from Robert Price, May 25 2021

A327070 Number of non-connected simple labeled graphs covering n vertices.

Original entry on oeis.org

1, 0, 0, 0, 3, 40, 745, 21028, 973889, 80133088, 12523299729, 3847333778244, 2341705361100633, 2821794389863015840, 6728707109106848947081, 31769173063866390661714996, 297278309767391164611330317921
Offset: 0

Views

Author

Gus Wiseman, Aug 24 2019

Keywords

Comments

We consider the empty graph to be neither connected (one component) nor disconnected (more than one component).

Examples

			The a(4) = 3 graphs:
  {{1,2},{3,4}}
  {{1,3},{2,4}}
  {{1,4},{2,3}}
		

Crossrefs

Column k = 0 of A327149.
The unlabeled version is A327075.
The non-covering version is A327199.

Programs

  • Mathematica
    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]]]]]]]]];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]!=1&]],{n,0,5}]

Formula

a(n) = A006129(n) - A001187(n), if we assume A001187(0) = 0 and A001187(1) = 0.
Inverse binomial transform of A327199.

A287689 Number of (non-null) connected induced subgraphs in the n-triangular graph.

Original entry on oeis.org

1, 7, 60, 968, 31737, 2069963, 267270032, 68629753640, 35171000942697, 36024807353574279, 73784587576805254652, 302228602363365451957792, 2475873310144021668263093201, 40564787336902311168400640561083, 1329227697997490307154018925966130304
Offset: 2

Views

Author

Eric W. Weisstein, May 29 2017

Keywords

Comments

Also the number of labeled simple graphs with n vertices whose edge-set is connected. - Gus Wiseman, Sep 11 2019

Examples

			From _Gus Wiseman_, Sep 11 2019: (Start)
The a(4) = 60 edge-sets:
  {12}  {12,13}  {12,13,14}  {12,13,14,23}  {12,13,14,23,24}
  {13}  {12,14}  {12,13,23}  {12,13,14,24}  {12,13,14,23,34}
  {14}  {12,23}  {12,13,24}  {12,13,14,34}  {12,13,14,24,34}
  {23}  {12,24}  {12,13,34}  {12,13,23,24}  {12,13,23,24,34}
  {24}  {13,14}  {12,14,23}  {12,13,23,34}  {12,14,23,24,34}
  {34}  {13,23}  {12,14,24}  {12,13,24,34}  {13,14,23,24,34}
        {13,34}  {12,14,34}  {12,14,23,24}
        {14,24}  {12,23,24}  {12,14,23,34}
        {14,34}  {12,23,34}  {12,14,24,34}
        {23,24}  {12,24,34}  {12,23,24,34}
        {23,34}  {13,14,23}  {13,14,23,24}
        {24,34}  {13,14,24}  {13,14,23,34}
                 {13,14,34}  {13,14,24,34}
                 {13,23,24}  {13,23,24,34}
                 {13,23,34}  {14,23,24,34}
                 {13,24,34}
                 {14,23,24}
                 {14,23,34}
                 {14,24,34}             {12,13,14,23,24,34}
                 {23,24,34}
(End)
		

Crossrefs

The unlabeled version is A292300.

Programs

  • Mathematica
    Table[With[{g = GraphData[{"Triangular", n}]}, Total[Boole[ConnectedGraphQ[Subgraph[g, #]] & /@ Subsets[VertexList[g]]]]], {n, 2, 5}] - 1
    (* Second program: *)
    g[n_] := g[n] = If[n==0, 1, 2^(n*(n-1)/2) - Sum[k*Binomial[n, k]*2^((n-k) * (n-k-1)/2)*g[k], {k, 1, n-1}]/n]; a[n_] := Sum[Binomial[n, i]*g[i], {i, 2, n}]; Table[a[n], {n, 2, 16}] (* Jean-François Alcover, Oct 02 2017, after Andrew Howroyd *)
  • PARI
    seq(n)={Vec(serlaplace(exp(x + O(x*x^n))*(-x+log(sum(k=0, n, 2^binomial(k, 2)*x^k/k!, O(x*x^n))))))} \\ Andrew Howroyd, Sep 11 2019

Formula

a(n) = Sum_{i=2..n} binomial(n,i) * A001187(i). - Andrew Howroyd, Jun 07 2017
E.g.f.: exp(x)*(-x + log(Sum_{k>=0} 2^binomial(k, 2)*x^k/k!)). - Andrew Howroyd, Sep 11 2019
a(n) = A006125(n) - A327199(n). - Gus Wiseman, Sep 11 2019

Extensions

Terms a(9) and beyond from Andrew Howroyd, Jun 07 2017

A327235 Number of unlabeled simple graphs with n vertices whose edge-set is not connected.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 14, 49, 234, 1476, 15405, 307536, 12651788, 1044977929, 167207997404, 50838593828724, 29156171171238607, 31484900549777534887, 64064043979274771429379, 246064055301339083624989655, 1788069981480210465772374023323, 24641385885409824180500407923934750
Offset: 0

Views

Author

Gus Wiseman, Sep 01 2019

Keywords

Examples

			The a(4) = 2 through a(6) = 14 edge-sets:
  {}       {}             {}
  {12,34}  {12,34}        {12,34}
           {12,35,45}     {12,34,56}
           {12,34,35,45}  {12,35,45}
                          {12,34,35,45}
                          {12,35,46,56}
                          {12,36,46,56}
                          {13,23,46,56}
                          {12,34,35,46,56}
                          {12,36,45,46,56}
                          {13,23,45,46,56}
                          {12,13,23,45,46,56}
                          {12,35,36,45,46,56}
                          {12,34,35,36,45,46,56}
		

Crossrefs

Unlabeled non-connected graphs are A000719.
Partial sums of A327075.
The labeled version is A327199.

Programs

  • 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 A327235(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))
        def a(n): return sum(mobius(n//d)*c(d) for d in divisors(n,generator=True))//n if n else 1
        return 1+b(n)-sum(a(i) for i in range(1,n+1)) # Chai Wah Wu, Jul 03 2024

Formula

a(n) = 1 + A000088(n) - Sum_{i = 1..n} A001349(i).

Extensions

a(20)-a(21) from Chai Wah Wu, Jul 03 2024

A327237 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices that, if the isolated vertices are removed, have cut-connectivity k.

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 1, 3, 3, 1, 4, 40, 15, 4, 1, 56, 660, 267, 35, 5, 1, 1031, 18756, 11022, 1862, 90, 6, 1
Offset: 0

Views

Author

Gus Wiseman, Sep 03 2019

Keywords

Comments

We define the cut-connectivity of a graph to be the minimum number of vertices that must be removed (along with any incident edges) to obtain a disconnected or empty graph, with the exception that a graph with one vertex has cut-connectivity 1. Except for complete graphs, this is the same as vertex-connectivity.

Examples

			Triangle begins:
   1
   1   0
   1   0   1
   1   3   3   1
   4  40  15   4   1
  56 660 267  35   5   1
		

Crossrefs

Row sums are A006125.
Column k = 0 is A327199.
The covering case is A327126.
Row sums without the first column are A287689.

Programs

  • Mathematica
    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]]]]]]]]];
    cutConnSys[vts_,eds_]:=If[Length[vts]==1,1,Min@@Length/@Select[Subsets[vts],Function[del,csm[DeleteCases[DeleteCases[eds,Alternatives@@del,{2}],{}]]!={Complement[vts,del]}]]];
    Table[Length[Select[Subsets[Subsets[Range[n],{2}]],cutConnSys[Union@@#,#]==k&]],{n,0,4},{k,0,n}]

Formula

Column-wise binomial transform of A327126.

Extensions

a(21)-a(27) from Jinyuan Wang, Jun 27 2020
Showing 1-5 of 5 results.