A001187 -id:A001187 - cp's OEIS frontend

A323817 Number of connected set-systems covering n vertices with no singletons.

1, 0, 1, 12, 1990, 67098648, 144115187673201808, 1329227995784915871895000743748659792, 226156424291633194186662080095093570015284114833799899656335137245499581360

Offset: 0

Gus Wiseman, Jan 30 2019

nonn

			The a(3) = 12 set-systems:
  {{1, 2, 3}}
  {{1, 2}, {1, 3}}
  {{1, 2}, {2, 3}}
  {{1, 3}, {2, 3}}
  {{1, 2}, {1, 2, 3}}
  {{1, 3}, {1, 2, 3}}
  {{2, 3}, {1, 2, 3}}
  {{1, 2}, {1, 3}, {2, 3}}
  {{1, 2}, {1, 3}, {1, 2, 3}}
  {{1, 2}, {2, 3}, {1, 2, 3}}
  {{1, 3}, {2, 3}, {1, 2, 3}}
  {{1, 2}, {1, 3}, {2, 3},{1, 2, 3}}
The A323816(4) - a(4) = 3 disconnected set-systems covering n vertices with no singletons:
  {{1, 2}, {3, 4}}
  {{1, 3}, {2, 4}}
  {{1, 4}, {2, 3}}

G. C. Greubel, Table of n, a(n) for n = 0..11

Cf. A001187, A016031, A048143, A092918, A293510, A317795, A323816 (not necessarily connected), A323818 (with singletons), A323819, A323820 (unlabeled case).

m:=10;
A323816:= func< n | (&+[(-1)^(n-j)*Binomial(n,j)*2^(2^j -j-1): j in [0..n]]) >;
f:= func< x | 1 + Log((&+[A323816(j)*x^j/Factorial(j): j in [0..m+2]])) >;
R:=PowerSeriesRing(Rationals(), m+1);
Coefficients(R!(Laplace( f(x) ))); // G. C. Greubel, Oct 05 2022

b:= n-> add(2^(2^(n-j)-n+j-1)*binomial(n, j)*(-1)^j, j=0..n):
a:= proc(n) option remember; b(n)-`if`(n=0, 0, add(
       k*binomial(n, k)*b(n-k)*a(k), k=1..n-1)/n)
    end:
seq(a(n), n=0..8);  # Alois P. Heinz, Jan 30 2019

nn=10;
ser=Sum[Sum[(-1)^(n-k)*Binomial[n,k]*2^(2^k-k-1),{k,0,n}]*x^n/n!,{n,0,nn}];
Table[SeriesCoefficient[1+Log[ser],{x,0,n}]*n!,{n,0,nn}]

m=10
def A323816(n): return sum((-1)^j*binomial(n,j)*2^(2^(n-j) -n+j-1) for j in range(n+1))
def A323817_list(prec):
    P. = PowerSeriesRing(QQ, prec)
    return P( 1 + log(sum(A323816(j)*x^j/factorial(j) for j in range(m+2))) ).egf_to_ogf().list()
A323817_list(m) # G. C. Greubel, Oct 05 2022

Logarithmic transform of A323816.

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Original entry on oeis.org

0, 0, 1, 0, 12, 200, 7680, 506856, 58934848, 12205506096, 4595039095680, 3210660115278000, 4240401342141499392, 10743530775519296581944, 52808688280248604235191296, 507730995579614277599205009240, 9603347831901155679455061048606720, 358743609478638769812094362544644831968

Offset: 0

Gus Wiseman, Aug 24 2019

nonn

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).

Andrew Howroyd, Table of n, a(n) for n = 0..50
Gus Wiseman, The a(4) = 12 graphs with exactly one bridge.

Column k = 1 of A327072.
The unlabeled version is A327074.
Connected graphs with no bridges are A007146.
Connected graphs whose bridges are all leaves are A322395.
Connected graphs with at least one bridge are A327071.
Cf. A001187, A006129, A052446, A095983, A327069, A327077, A327108, A327111, A327145, A327146.

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&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==1&]],{n,0,5}]

\\ See A095983.
seq(n)={my(p=x*deriv(log(sum(k=0, n-1, 2^binomial(k, 2) * x^k / k!) + O(x^n)))); Vec(serlaplace(log(x/serreverse(x*exp(p)))^2/2), -(n+1)) } \\ Andrew Howroyd, Dec 28 2020

E.g.f.: (x + Sum_{k>=2} A095983(k)*x^k/(k-1)!)^2/2. - Andrew Howroyd, Aug 25 2019

Terms a(6) and beyond from Andrew Howroyd, Aug 25 2019

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

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 3, 12, 15, 10, 1, 40, 180, 297, 180, 60, 10, 1

Offset: 0

Gus Wiseman, Aug 27 2019

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

			Triangle begins:
   1
   {}
   0   1
   0   0   3   1
   3  12  15  10   1
  40 180 297 180  60  10   1

Row sums are A006129.
Column k = 0 is A327070.
Column k = 1 is A327079.
The corresponding triangle for vertex-connectivity is A327126.
The corresponding triangle for spanning edge-connectivity is A327069.
The non-covering version is A327148.
The unlabeled version is A327201.
Cf. A001187, A263296, A322338, A322395, A326787, A327097, A327099, A327102, A327125, A327129, A327144.

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]]]]]]]]];
eConn[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}]],Union@@#==Range[n]&&eConn[#]==k&]],{n,0,4},{k,0,Binomial[n,2]}]//.{foe___,0}:>{foe}

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

A327231 Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).

Original entry on oeis.org

0, 0, 1, 3, 18, 250, 5475, 191541, 11065572, 1104254964, 201167132805, 69828691941415, 47150542741904118, 62354150876493659118, 161919876753750972738791, 827272271567137357352991705, 8331016130913639432634637862600, 165634930763383717802534343776893928

Offset: 0

Gus Wiseman, Sep 01 2019

nonn

A bridge is an edge whose removal disconnected the graph, while an endpoint is a vertex belonging to only one edge. The non-spanning edge-connectivity of a graph is the minimum number of edges that must be removed to obtain a graph whose edge-set is disconnected or empty.

			The a(2) = 1 through a(4) = 18 edge-sets:
  {12}  {12}  {12}
        {13}  {13}
        {23}  {14}
              {23}
              {24}
              {34}
              {12,13,24}
              {12,13,34}
              {12,14,23}
              {12,14,34}
              {12,23,34}
              {12,24,34}
              {13,14,23}
              {13,14,24}
              {13,23,24}
              {13,24,34}
              {14,23,24}
              {14,23,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Column k = 1 of A327148.
The covering version is A327079.
Connected bridged graphs (spanning edge-connectivity 1) are A327071.
BII-numbers of set-systems with non-spanning edge-connectivity 1 are A327099.
Covering set-systems with non-spanning edge-connectivity 1 are A327129.
Cf. A001187, A052446, A322395, A327072, A327073, A327102.

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]]]]]]]]];
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[#]==1&]],{n,0,4}]

Binomial transform of A327079.

Terms a(6) and beyond from Andrew Howroyd, Sep 11 2019

A371294 Numbers whose binary indices are connected and pairwise indivisible, where two numbers are connected iff they have a common factor. A hybrid ranking sequence for connected antichains of multisets.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 40, 64, 128, 160, 256, 288, 296, 416, 512, 520, 544, 552, 640, 672, 800, 808, 928, 1024, 2048, 2176, 2304, 2432, 2560, 2688, 2816, 2944, 4096, 8192, 8200, 8224, 8232, 8320, 8352, 8480, 8488, 8608, 8704, 8712, 8736, 8744, 8832, 8864, 8992

Offset: 1

Gus Wiseman, Mar 28 2024

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

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.

			The terms together with their prime indices of binary indices begin:
    1: {{}}
    2: {{1}}
    4: {{2}}
    8: {{1,1}}
   16: {{3}}
   32: {{1,2}}
   40: {{1,1},{1,2}}
   64: {{4}}
  128: {{1,1,1}}
  160: {{1,2},{1,1,1}}
  256: {{2,2}}
  288: {{1,2},{2,2}}
  296: {{1,1},{1,2},{2,2}}
  416: {{1,2},{1,1,1},{2,2}}
  512: {{1,3}}
  520: {{1,1},{1,3}}
  544: {{1,2},{1,3}}
  552: {{1,1},{1,2},{1,3}}
  640: {{1,1,1},{1,3}}
  672: {{1,2},{1,1,1},{1,3}}
  800: {{1,2},{2,2},{1,3}}
  808: {{1,1},{1,2},{2,2},{1,3}}
  928: {{1,2},{1,1,1},{2,2},{1,3}}

Connected case of A087086, relatively prime A328671.
For binary indices of binary indices we have A326750, non-primitive A326749.
For prime indices of prime indices we have A329559, non-primitive A305078.
Primitive case of A371291 = positions of ones in A371452.
For binary indices of prime indices we have A371445, non-primitive A325118.
A001187 counts connected graphs.
A007718 counts non-isomorphic connected multiset partitions.
A048143 counts connected antichains of sets.
A048793 lists binary indices, A000120 length, A272020 reverse, A029931 sum.
A070939 gives length of binary expansion.
A096111 gives product of binary indices.
A326964 counts connected set-systems, covering A323818.
Cf. A001222, A051026, A285572, A303362, A304713, A305079, A316476, A319496, A319719, A326704, A371446.

stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],stableQ[bpe[#],Divisible]&&connectedQ[prix/@bpe[#]]&]

Intersection of A087086 and A371291.

A125207 Total number of connected components in all subgraphs obtained from the complete labeled graph K_n by removing zero or more edges.

Original entry on oeis.org

1, 3, 13, 98, 1398, 39956, 2354240, 286394544, 71225744048, 35884971729760, 36419817759267072, 74221711070826087424, 303193538300703211111936, 2480118087478081928075065344, 40601989279034990139321984265216, 1329877330680067685563700135615633408

Offset: 1

Max Alekseyev, Nov 23 2006

nonn

a(n)/A006125(n) is the expected number of connected components in a simple labeled graph on n vertices. - Geoffrey Critzer, May 09 2011

			For n=2, we have two graph on two vertices: complete and empty, the former has one connected component while the latter has two connected components. The total number of connected components is 3, which is a(2).

Alois P. Heinz, Table of n, a(n) for n = 1..82

Cf. A001187, A125205, A125206, A143543.

f[list_]:= Total[Table[i list[[i]],{i,1,Length[list]}]];
a= Sum[2^Binomial[n,2] x^n/n!,{n,0,20}];
Map[f, Transpose[Table[Rest[Range[0, 20]! CoefficientList[Series[Log[a]^k/k!, {x, 0, 20}],x]], {k, 1, 20}]]] (* Geoffrey Critzer, May 09 2011 *)

G=sum(n=0,30,2^(n*(n-1)/2)*x^n/n!) + O(x^31); v=Vec(G*log(G)); for(i=1,length(v),v[i]*=i!); print(v)

E.g.f.: (F(x)-1)*exp(F(x)-1) = G(x)*log(G(x)) where G(x) = Sum_{n>=0} 2^(n(n-1)/2) * x^n/n! and F(x) = 1+log(G(x)) is the e.g.f. of A001187.

a(n) = Sum_{k=1..n} k * A143543(n,k). - Alois P. Heinz, Feb 02 2024

A322064 Number of ways to choose a stable partition of a simple connected graph with n vertices.

Original entry on oeis.org

1, 1, 1, 7, 141, 6533, 631875, 123430027, 48659732725, 39107797223409, 64702785181953175, 221636039917857648631, 1575528053913118966200441, 23249384407499950496231003021, 711653666389829384034090082068939, 45128328085994437067694854477617868995

Offset: 0

Gus Wiseman, Nov 25 2018

nonn

A stable partition of a graph is a set partition of the vertices where no non-singleton edge has both ends in the same block.

			The a(3) = 7 stable partitions. The simple connected graph is on top, and below is a list of all its stable partitions.
  {1,3}{2,3}     {1,2}{2,3}     {1,2}{1,3}     {1,2}{1,3}{2,3}
  --------       --------       --------       --------
  {{1,2},{3}}    {{1,3},{2}}    {{1},{2,3}}    {{1},{2},{3}}
  {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}

Andrew Howroyd, Table of n, a(n) for n = 0..75

Row sums of A322278.

Cf. A000110, A000569, A001187, A006125, A048143, A229048, A240936, A245883, A277203, A321911, A321979, A322063, A322065.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Union[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Sum[Length[Select[Subsets[Complement[Subsets[Range[n],{2}],Union@@Subsets/@stn]],And[Union@@#==Range[n],Length[csm[#]]==1]&]],{stn,sps[Range[n]]}],{n,5}]

\\ See A322278 for M.
seq(n)={concat([1], (M(n)*vectorv(n,i,1))~)} \\ Andrew Howroyd, Dec 01 2018

Terms a(7) and beyond from Andrew Howroyd, Dec 01 2018

A322278 Triangle read by rows: T(n,k) is the number of k-colored connected graphs on n labeled nodes up to permutation of the colors.

Original entry on oeis.org

1, 0, 1, 0, 3, 4, 0, 19, 84, 38, 0, 195, 2470, 3140, 728, 0, 3031, 108390, 307390, 186360, 26704, 0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256, 0, 2086099, 726782784, 9030799218, 20784069600, 14401134944, 3463311488, 251548592

Offset: 1

Andrew Howroyd, Dec 01 2018

Equivalently, the number of ways to choose a stable partition of a simple connected graph on n labeled nodes with k parts. See A322064 for the definition of stable partition.

			Triangle begins:
  1;
  0,     1;
  0,     3,       4;
  0,    19,      84,       38;
  0,   195,    2470,     3140,      728;
  0,  3031,  108390,   307390,   186360,    26704;
  0, 67263, 7192444, 42747460, 52630060, 18926544, 1866256;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Row sums are A322064.
Columns k=2..4 are A001832(for n > 1), A322330, A322331.
Right diagonal is A001187.
Cf. A058843, A058875, A322279, A322280.

M(n, K=n)={
  my(p=sum(j=0, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n));
  my(q=sum(j=0, n, x^j*2^binomial(j, 2)) + O(x*x^n));
  my(W=vector(K, k, Col(serlaplace(log(serconvol(q, p^k))))));
  Mat(vector(K, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*W[i])/k!));
}
my(T=M(7)); for(n=1, #T, print(T[n, 1..n]))

T(n,k) = (1/k!)*Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*A322279(n,j).

A326964 Number of connected set-systems covering a subset of {1..n}.

Original entry on oeis.org

1, 2, 7, 112, 32253, 2147316942, 9223372023968335715, 170141183460469231667123699322514272668, 5789604461865809771178549250434395393752402807429031284280914691514037561273

Offset: 0

Gus Wiseman, Aug 10 2019

nonn

A set-system is a finite set of finite nonempty sets.

			The a(0) = 1 through a(2) = 7 set-systems:
  {}    {}     {}
        {{1}}  {{1}}
               {{2}}
               {{1,2}}
               {{1},{1,2}}
               {{2},{1,2}}
               {{1},{2},{1,2}}

Covering sets of subsets are A000371.
Connected graphs are A001187.
The unlabeled version is A309667.
The BII-numbers of connected set-systems are A326749.
The covering case is A323818.
Cf. A007718, A048143, A058891, A092918, A300913, A304716, A326866, A326948.

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],{1,n}]],Length[csm[#]]<=1&]],{n,0,4}]

Binomial transform of A323818.

A327072 Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.

Original entry on oeis.org

1, 1, 0, 0, 1, 0, 1, 0, 3, 0, 10, 12, 0, 16, 0, 253, 200, 150, 0, 125, 0, 11968, 7680, 3600, 2160, 0, 1296, 0, 1047613, 506856, 190365, 68600, 36015, 0, 16807, 0, 169181040, 58934848, 16353792, 4695040, 1433600, 688128, 0, 262144, 0, 51017714393, 12205506096, 2397804444, 500828832, 121706550, 33067440, 14880348, 0, 4782969, 0

Offset: 0

Gus Wiseman, Aug 24 2019

A bridge is an edge that, if removed without removing any incident vertices, disconnects the graph. Connected graphs with no bridges are counted by A095983 (2-edge-connected graphs).

Warning: In order to be consistent with A001187, we have treated the n = 0 and n = 1 cases in ways that are not consistent with A095983.

			Triangle begins:
    1
    1   0
    0   1   0
    1   0   3   0
   10  12   0  16   0
  253 200 150   0 125   0

Andrew Howroyd, Table of n, a(n) for n = 0..1325
Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.

Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.
Column k = 1 is A327073.
Column k = n - 1 is A000272.
Row sums are A001187.
The unlabeled version is A327077.
Row sums without the first column are A327071.
Cf. A001349, A007146, A052446, A054592, A059166, A322395, A327069, A327148.

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[If[n<=1&&k==0,1,Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]==1&&Count[Table[Length[Union@@Delete[#,i]]1,{i,Length[#]}],True]==k&]]],{n,0,4},{k,0,n}]

\\ p is e.g.f. of A053549.
T(n)={my(p=x*deriv(log(sum(k=0, n, 2^binomial(k, 2) * x^k / k!) + O(x*x^n))), v=Vec(1+serreverse(serreverse(log(x/serreverse(x*exp(p))))/exp(x*y+O(x^n))))); vector(#v, k, max(0,k-2)!*Vecrev(v[k], k)) }
{ my(A=T(8)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Dec 28 2020

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

cp's OEIS Frontend

A323817 Number of connected set-systems covering n vertices with no singletons.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A327073 Number of labeled simple connected graphs with n vertices and exactly one bridge.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A327231 Number of labeled simple connected graphs covering a subset of {1..n} with at least one non-endpoint bridge (non-spanning edge-connectivity 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A371294 Numbers whose binary indices are connected and pairwise indivisible, where two numbers are connected iff they have a common factor. A hybrid ranking sequence for connected antichains of multisets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A125207 Total number of connected components in all subgraphs obtained from the complete labeled graph K_n by removing zero or more edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A322064 Number of ways to choose a stable partition of a simple connected graph with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica