A322395 Number of labeled simple connected graphs with n vertices whose bridges are all leaves, meaning at least one end of any bridge is an endpoint of the graph.

1, 1, 1, 4, 26, 548, 22504, 1708336, 241874928, 65285161232, 34305887955616, 35573982726480064, 73308270568902715136, 301210456065963448091072, 2471487759846321319412778624, 40526856087731237340916330352896, 1328570640536613080046570271722309632

Offset

0,4

Links

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

Eric Weisstein's World of Mathematics, Graph Bridge

Eric Weisstein's World of Mathematics, Endpoint

Formula

a(n) = n + Sum_{k=1..n} binomial(n,k)*A095983(k)*k^(n-k) for n >= 3. - Andrew Howroyd, Dec 07 2018

Mathematica

nmax = 16;
seq[n_] := Module[{v, p, q, c}, v[_] = 0; p = x*D[#, x]& @ Log[Sum[ 2^Binomial[k, 2]*x^k/k!, {k, 0, n}] + O[x]^(n + 1)]; q = x*E^p; p -= q; For[k = 3, k <= n, k++, c = Coefficient[p, x, k]; v[k] = c*(k - 1)!; p -= c*q^k]; Join[{0}, Array[v, n]]];
A095983 = seq[nmax];
a[n_] := If[n<3, 1, n+Sum[Binomial[n, k]*A095983[[k+1]]*k^(n-k), {k, 1, n}]];
a /@ Range[0, nmax] (* Jean-François Alcover, Jan 07 2021, after Andrew Howroyd *)

Crossrefs

Cf. A001187, A006125, A007146, A013922, A054921, A095983, A322338, A322387, A322394.

Sequence in context: A328419 A194926 A167147 * A326264 A132488 A320626

Adjacent sequences: A322392 A322393 A322394 * A322396 A322397 A322398

Keyword

nonn

Author

Gus Wiseman, Dec 06 2018

Extensions

a(6)-a(16) from Andrew Howroyd, Dec 07 2018

Status

approved