cp's OEIS Frontend

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

%I A327072 #10 Dec 29 2020 03:19:58
%S A327072 1,1,0,0,1,0,1,0,3,0,10,12,0,16,0,253,200,150,0,125,0,11968,7680,3600,
%T A327072 2160,0,1296,0,1047613,506856,190365,68600,36015,0,16807,0,169181040,
%U A327072 58934848,16353792,4695040,1433600,688128,0,262144,0,51017714393,12205506096,2397804444,500828832,121706550,33067440,14880348,0,4782969,0
%N A327072 Triangle read by rows where T(n,k) is the number of labeled simple connected graphs with n vertices and exactly k bridges.
%C A327072 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).
%C A327072 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.
%H A327072 Andrew Howroyd, <a href="/A327072/b327072.txt">Table of n, a(n) for n = 0..1325</a>
%H A327072 Gus Wiseman, <a href="/A327072/a327072.png">The 10 + 12 + 16 graphs counted in row n = 4.</a>
%e A327072 Triangle begins:
%e A327072     1
%e A327072     1   0
%e A327072     0   1   0
%e A327072     1   0   3   0
%e A327072    10  12   0  16   0
%e A327072   253 200 150   0 125   0
%t A327072 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]]]]]]]]];
%t A327072 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}]
%o A327072 (PARI) \\ p is e.g.f. of A053549.
%o A327072 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)) }
%o A327072 { my(A=T(8)); for(n=1, #A, print(A[n])) } \\ _Andrew Howroyd_, Dec 28 2020
%Y A327072 Column k = 0 is A095983, if we assume A095983(0) = A095983(1) = 1.
%Y A327072 Column k = 1 is A327073.
%Y A327072 Column k = n - 1 is A000272.
%Y A327072 Row sums are A001187.
%Y A327072 The unlabeled version is A327077.
%Y A327072 Row sums without the first column are A327071.
%Y A327072 Cf. A001349, A007146, A052446, A054592, A059166, A322395, A327069, A327148.
%K A327072 nonn,tabl
%O A327072 0,9
%A A327072 _Gus Wiseman_, Aug 24 2019
%E A327072 Terms a(21) and beyond from _Andrew Howroyd_, Dec 28 2020