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

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,9

Comments

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.

Links

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

Gus Wiseman, The 10 + 12 + 16 graphs counted in row n = 4.

Example

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

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

Prog

(PARI) \\ 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

Crossrefs

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.

Sequence in context: A119957 A028852 A319202 * A327377 A095200 A090460

Adjacent sequences: A327069 A327070 A327071 * A327073 A327074 A327075

Keyword

nonn,tabl

Author

Gus Wiseman, Aug 24 2019

Extensions

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

Status

approved