A002218 -id:A002218 - cp's OEIS frontend

A322110 Number of non-isomorphic connected multiset partitions of weight n that cannot be capped by a tree.

1, 1, 3, 6, 15, 32, 86, 216, 628, 1836, 5822

Offset: 0

Gus Wiseman, Nov 26 2018

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

The density of a multiset partition is defined to be the sum of numbers of distinct elements in each part, minus the number of parts, minus the total number of distinct elements in the whole partition. A multiset partition is a tree if it has more than one part, is connected, and has density -1. A cap is a certain kind of non-transitive coarsening of a multiset partition. For example, the four caps of {{1,1},{1,2},{2,2}} are {{1,1},{1,2},{2,2}}, {{1,1},{1,2,2}}, {{1,1,2},{2,2}}, {{1,1,2,2}}. - Gus Wiseman, Feb 05 2021

			The multiset partition C = {{1,1},{1,2,3},{2,3,3}} is not a tree but has the cap {{1,1},{1,2,3,3}} which is a tree, so C is not counted under a(8).
Non-isomorphic representatives of the a(1) = 1 through a(5) = 32 multiset partitions:
  {{1}}  {{1,1}}    {{1,1,1}}      {{1,1,1,1}}        {{1,1,1,1,1}}
         {{1,2}}    {{1,2,2}}      {{1,1,2,2}}        {{1,1,2,2,2}}
         {{1},{1}}  {{1,2,3}}      {{1,2,2,2}}        {{1,2,2,2,2}}
                    {{1},{1,1}}    {{1,2,3,3}}        {{1,2,2,3,3}}
                    {{2},{1,2}}    {{1,2,3,4}}        {{1,2,3,3,3}}
                    {{1},{1},{1}}  {{1},{1,1,1}}      {{1,2,3,4,4}}
                                   {{1,1},{1,1}}      {{1,2,3,4,5}}
                                   {{1},{1,2,2}}      {{1},{1,1,1,1}}
                                   {{1,2},{1,2}}      {{1,1},{1,1,1}}
                                   {{2},{1,2,2}}      {{1},{1,2,2,2}}
                                   {{3},{1,2,3}}      {{1,2},{1,2,2}}
                                   {{1},{1},{1,1}}    {{2},{1,1,2,2}}
                                   {{1},{2},{1,2}}    {{2},{1,2,2,2}}
                                   {{2},{2},{1,2}}    {{2},{1,2,3,3}}
                                   {{1},{1},{1},{1}}  {{2,2},{1,2,2}}
                                                      {{2,3},{1,2,3}}
                                                      {{3},{1,2,3,3}}
                                                      {{4},{1,2,3,4}}
                                                      {{1},{1},{1,1,1}}
                                                      {{1},{1,1},{1,1}}
                                                      {{1},{1},{1,2,2}}
                                                      {{1},{2},{1,2,2}}
                                                      {{2},{1,2},{1,2}}
                                                      {{2},{1,2},{2,2}}
                                                      {{2},{2},{1,2,2}}
                                                      {{2},{3},{1,2,3}}
                                                      {{3},{1,3},{2,3}}
                                                      {{3},{3},{1,2,3}}
                                                      {{1},{1},{1},{1,1}}
                                                      {{1},{2},{2},{1,2}}
                                                      {{2},{2},{2},{1,2}}
                                                      {{1},{1},{1},{1},{1}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Non-isomorphic tree multiset partitions are counted by A321229.
The weak-antichain case is counted by A322117.
The case without singletons is counted by A322118.
Cf. A002218, A007718, A013922, A030019, A056156, A275307, A304118, A304382, A304887, A305052, A305079, A321194.

Corrected by Gus Wiseman, Jan 27 2021

A322118 Number of non-isomorphic connected multiset partitions of weight n with no singletons that cannot be capped by a tree.

Original entry on oeis.org

1, 1, 2, 3, 7, 11, 29, 55, 155, 386, 1171

Offset: 0

Gus Wiseman, Nov 26 2018

The density of a multiset partition is defined to be the sum of numbers of distinct elements in each part, minus the number of parts, minus the total number of distinct elements in the whole partition. A multiset partition is a tree if it has more than one part, is connected, and has density -1. A cap is a certain kind of non-transitive coarsening of a multiset partition. For example, the four caps of {{1,1},{1,2},{2,2}} are {{1,1},{1,2},{2,2}}, {{1,1},{1,2,2}}, {{1,1,2},{2,2}}, {{1,1,2,2}}. - Gus Wiseman, Feb 05 2021

			The multiset partition C = {{1,1},{1,2,3},{2,3,3}} is not a tree but has the cap {{1,1},{1,2,3,3}} which is a tree, so C is not counted under a(8).
Non-isomorphic representatives of the a(2) = 2 through a(6) = 29 multiset partitions:
  {{1,1}}  {{1,1,1}}  {{1,1,1,1}}    {{1,1,1,1,1}}    {{1,1,1,1,1,1}}
  {{1,2}}  {{1,2,2}}  {{1,1,2,2}}    {{1,1,2,2,2}}    {{1,1,1,2,2,2}}
           {{1,2,3}}  {{1,2,2,2}}    {{1,2,2,2,2}}    {{1,1,2,2,2,2}}
                      {{1,2,3,3}}    {{1,2,2,3,3}}    {{1,1,2,2,3,3}}
                      {{1,2,3,4}}    {{1,2,3,3,3}}    {{1,2,2,2,2,2}}
                      {{1,1},{1,1}}  {{1,2,3,4,4}}    {{1,2,2,3,3,3}}
                      {{1,2},{1,2}}  {{1,2,3,4,5}}    {{1,2,3,3,3,3}}
                                     {{1,1},{1,1,1}}  {{1,2,3,3,4,4}}
                                     {{1,2},{1,2,2}}  {{1,2,3,4,4,4}}
                                     {{2,2},{1,2,2}}  {{1,2,3,4,5,5}}
                                     {{2,3},{1,2,3}}  {{1,2,3,4,5,6}}
                                                      {{1,1},{1,1,1,1}}
                                                      {{1,1,1},{1,1,1}}
                                                      {{1,1,2},{1,2,2}}
                                                      {{1,2},{1,1,2,2}}
                                                      {{1,2},{1,2,2,2}}
                                                      {{1,2},{1,2,3,3}}
                                                      {{1,2,2},{1,2,2}}
                                                      {{1,2,3},{1,2,3}}
                                                      {{1,2,3},{2,3,3}}
                                                      {{1,3,4},{2,3,4}}
                                                      {{2,2},{1,1,2,2}}
                                                      {{2,2},{1,2,2,2}}
                                                      {{2,3},{1,2,3,3}}
                                                      {{3,3},{1,2,3,3}}
                                                      {{3,4},{1,2,3,4}}
                                                      {{1,1},{1,1},{1,1}}
                                                      {{1,2},{1,2},{1,2}}
                                                      {{1,2},{1,3},{2,3}}

Gus Wiseman, Every Clutter Is a Tree of Blobs, The Mathematica Journal, Vol. 19, 2017.

Non-isomorphic tree multiset partitions are counted by A321229, or A321231 without singletons.
The version with singletons is A322110.
The weak-antichain case is counted by A322138, or A322117 with singletons.
Cf. A002218, A007718, A013922, A030019, A275307, A293994, A304118, A304382, A304887, A305079, A319719, A319721, A321194.

Definition corrected by Gus Wiseman, Feb 05 2021

A322139 Number of labeled 2-connected simple graphs with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 1, 0, 1, 3, 18, 131, 1180, 12570, 154535, 2151439, 33431046, 573197723, 10743619285, 218447494812, 4787255999220, 112454930390211, 2818138438707516, 75031660452368001, 2114705500316025737, 62890323682634277951, 1967901134191778583146, 64623905086814216468839

Offset: 0

Gus Wiseman, Nov 27 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..100
Gus Wiseman, The a(6) = 131 labeled 2-connected graphs with 6 edges.

Cf. A002218, A013922, A123534, A275307, A291841, A304118, A304887, A322110, A322117, A322118, A322137, A322138.

seq(n)={Vec(1 + vecsum(Vec(serlaplace(log(x/serreverse(x*deriv(log(sum(k=0, n, (1 + y + O(y*y^n))^binomial(k, 2) * x^k / k!) + O(x*x^n)))))))))} \\ Andrew Howroyd, Nov 29 2018

a(n) = Sum_{i=3..n} A123534(i, n). - Andrew Howroyd, Nov 30 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 29 2018

A327805 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and vertex-connectivity >= k.

Original entry on oeis.org

1, 1, 0, 2, 1, 0, 4, 2, 1, 0, 11, 6, 3, 1, 0, 34, 21, 10, 3, 1, 0, 156, 112, 56, 17, 4, 1, 0, 1044, 853, 468, 136, 25, 4, 1, 0, 12346, 11117, 7123, 2388, 384, 39, 5, 1, 0, 274668, 261080, 194066, 80890, 14480, 1051, 59, 5, 1, 0, 12005168, 11716571, 9743542, 5114079, 1211735, 102630, 3211, 87, 6, 1, 0

Offset: 0

Gus Wiseman, Sep 26 2019

The vertex-connectivity of a graph is the minimum number of vertices that must be removed (along with any incident edges) to obtain a non-connected graph or singleton. Note that this means a single node has vertex-connectivity 0.

			Triangle begins:
   1
   1  0
   2  1  0
   4  2  1  0
  11  6  3  1  0
  34 21 10  3  1  0

Gus Wiseman, The graphs counted in row n = 4 (isolated vertices not shown).

Row-wise partial sums of A259862.
The labeled version is A327363.
The covering case is A327365, from which this sequence differs only in the k = 0 column.
Column k = 0 is A000088 (graphs).
Column k = 1 is A001349 (connected graphs), if we assume A001349(0) = A001349(1) = 0.
Column k = 2 is A002218 (2-connected graphs), if we assume A002218(2) = 0.
The triangle for vertex-connectivity exactly k is A259862.
Cf. A326786, A327051, A327114, A327125, A327126, A327127, A327334.

T(n,k) = Sum_{j=k..n} A259862(n,j).

Terms a(21) and beyond from Andrew Howroyd, Dec 26 2020

A086217 Number of 5-connected graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 4, 39, 1051, 102630, 22331311, 8491843895

Offset: 1

Eric W. Weisstein, Jul 12 2003

Travis Hoppe and Anna Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
Jens M. Schmidt, Data files in graph6 format
Eric Weisstein's World of Mathematics, k-Connected Graph

Cf. A002218, A052443, A052445, A086216, A259862, A324234, A324240.

a(n) = A324240(n) + A324234(n). - Andrew Howroyd, Sep 04 2019

a(n) = A086216(n) - A052445(n). - Jean-François Alcover, Sep 13 2019, after Andrew Howroyd in A086216

Offset corrected by Travis Hoppe, Apr 11 2014
a(10) from the Encyclopedia of Finite Graphs (Travis Hoppe and Anna Petrone), Apr 11 2014
a(11) by Jens M. Schmidt, Feb 20 2019
a(12) added by Georg Grasegger, Jan 07 2025

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

Original entry on oeis.org

1, 1, 3, 10, 12, 16, 238, 215, 150, 125, 11368, 7740, 4140, 2160, 1296, 1014888, 509446, 205065, 84035, 36015, 16807, 166537616, 59409952, 17393152, 5393920, 1863680, 688128, 262144, 50680432112, 12321597708, 2516756508, 563570217, 148803480, 45467730

Offset: 1

Gus Wiseman, Aug 03 2018

			Triangle begins:
        1
        1       3
       10      12      16
      238     215     150     125
    11368    7740    4140    2160    1296
  1014888  509446  205065   84035   36015   16807

Row sums are A001187. First column is A013922. Last column is A000272.

Cf. A002218, A030019, A048143, A134954, A275307, A293510, A317631, A317632, A317634, A317635, A317672, A317677.

blg={0,1,1,10,238,11368,1014888,166537616,50680432112,29107809374336} (*A013922*);
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}]

A322138 Number of non-isomorphic weight-n blobs (2-connected weak antichains) of multisets with no singletons.

Original entry on oeis.org

1, 0, 2, 3, 7, 7, 20, 26, 78, 184, 553

Offset: 0

Gus Wiseman, Nov 27 2018

The weight of a multiset partition is the sum of sizes of its parts. Weight is generally not the same as number of vertices.

			Non-isomorphic representatives of the a(2) = 2 through a(7) = 26 blobs:
  {{11}}  {{111}}  {{1111}}    {{11111}}  {{111111}}      {{1111111}}
  {{12}}  {{122}}  {{1122}}    {{11222}}  {{111222}}      {{1112222}}
          {{123}}  {{1222}}    {{12222}}  {{112222}}      {{1122222}}
                   {{1233}}    {{12233}}  {{112233}}      {{1122333}}
                   {{1234}}    {{12333}}  {{122222}}      {{1222222}}
                   {{11}{11}}  {{12344}}  {{122333}}      {{1222333}}
                   {{12}{12}}  {{12345}}  {{123333}}      {{1223333}}
                                          {{123344}}      {{1223344}}
                                          {{123444}}      {{1233333}}
                                          {{123455}}      {{1233444}}
                                          {{123456}}      {{1234444}}
                                          {{111}{111}}    {{1234455}}
                                          {{112}{122}}    {{1234555}}
                                          {{122}{122}}    {{1234566}}
                                          {{123}{123}}    {{1234567}}
                                          {{123}{233}}    {{112}{1222}}
                                          {{134}{234}}    {{122}{1233}}
                                          {{11}{11}{11}}  {{123}{2233}}
                                          {{12}{12}{12}}  {{123}{2333}}
                                          {{12}{13}{23}}  {{123}{2344}}
                                                          {{134}{2344}}
                                                          {{145}{2345}}
                                                          {{223}{1233}}
                                                          {{344}{1234}}
                                                          {{12}{13}{233}}
                                                          {{13}{14}{234}}

Cf. A002218, A007718, A013922, A275307, A286520, A293994, A304118, A304887, A319719, A322110, A322117, A322118.

A289471 Number of planar strictly 2-connected graphs on n edges.

Original entry on oeis.org

1, 0, 1, 1, 2, 3, 7, 15, 39, 106, 316, 1030, 3553, 13006, 49780, 197281, 804649, 3358885, 14289507, 61769577

Offset: 1

Ed Pegg Jr, Jul 06 2017

Cf. A002218, A002840, A289470, A343869.

a(n) = A343869(n) - A002840(n). - Andrew Howroyd, May 04 2021

a(12)-a(13) corrected and a(14)-a(20) from Andrew Howroyd, May 04 2021

A322140 Number of labeled 2-connected multigraphs with n edges (the vertices are {1,2,...,k} for some k).

Original entry on oeis.org

1, 1, 1, 2, 7, 37, 262, 2312, 24338, 296928, 4112957, 63692909, 1089526922, 20389411551, 414146189901, 9070116944468, 212983762029683, 5336570227705763, 142083405456873290, 4004953714929148655, 119128974685786590410, 3728639072095285867881

Offset: 0

Gus Wiseman, Nov 27 2018

nonn

We consider a single edge to be 2-connected, so a(1) = 1.

Andrew Howroyd, Table of n, a(n) for n = 0..100
Gus Wiseman, The a(5) = 37 labeled 2-connected multigraphs with 5 edges.

Cf. A002218, A002905, A013922, A275307, A291841, A304118, A304887, A322110, A322117, A322118, A322137, A322138.

seq(n)={Vec(1 + vecsum(Vec(serlaplace(log(x/serreverse(x*deriv(log(sum(k=0, n, 1/(1 - y + O(y*y^n))^binomial(k, 2) * x^k / k!) + O(x*x^n)))))))))} \\ Andrew Howroyd, Nov 29 2018

Terms a(7) and beyond from Andrew Howroyd, Nov 29 2018

A324234 Number of simple non-isomorphic n-vertex graphs of connectivity 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 34, 992, 99419, 21500415, 8004834513

Offset: 1

Jens M. Schmidt, Feb 19 2019

Jens M. Schmidt, Data files in graph6 format

Column k=5 of A259862.

Cf. A052443, A002218.

a(12) added by Brendan McKay, Sep 01 2023

cp's OEIS Frontend

A322110 Number of non-isomorphic connected multiset partitions of weight n that cannot be capped by a tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A322118 Number of non-isomorphic connected multiset partitions of weight n with no singletons that cannot be capped by a tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A322139 Number of labeled 2-connected simple graphs with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A327805 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs with n vertices and vertex-connectivity >= k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A086217 Number of 5-connected graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A322138 Number of non-isomorphic weight-n blobs (2-connected weak antichains) of multisets with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

A289471 Number of planar strictly 2-connected graphs on n edges.

Views

Author

Keywords

Crossrefs

Formula

Extensions

A322140 Number of labeled 2-connected multigraphs with n edges (the vertices are {1,2,...,k} for some k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A324234 Number of simple non-isomorphic n-vertex graphs of connectivity 5.