A356375 Number of unlabeled centered trees with n nodes that have exactly one diametral path (up to direction of traversal).

0, 1, 0, 1, 0, 1, 2, 5, 9, 21, 44, 107, 247, 607, 1465, 3649, 9087, 23059, 58831, 151832, 394074, 1030492, 2708343, 7157735, 19002282, 50676945, 135691504, 364725995, 983775878, 2662271414, 7226368722, 19670528467, 53685042694, 146879757368, 402786655780, 1106968400532

Offset

0,7

Comments

A diametral path in a tree is a path of maximum length. A diametral path in a centered tree is necessarily of even length. Its endpoints are leaves and its middle point is the center of the tree. A centered tree with exactly one diametral path of length 2m can be decomposed into a rooted tree of height at most m-1 along with exactly 2 rooted trees of height exactly m-1. It appears that almost all centered trees (A000676) have exactly one diametral path.

Links

Table of n, a(n) for n=0..35.

J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)

Index entries for sequences related to trees

Mathematica

nn = 35; S[0, x_] := x; S[k_, x_] := Total[Nest[CoefficientList[Series[Product[1/(1 - x^i)^#[[i]], {i, 1, Length[#]}], {x, 0, nn}], x] &, {1}, k] Table[x^i, {i, 1, nn + 1}]]; R[0, x] := x; R[k_, x_] := S[k, x] - S[k - 1, x]; ReplacePart[ Sum[PadRight[
   CoefficientList[Series[S[m, x] (R[m, x]^2 + (R[m, x] /. x -> x^2))/2, {x, 0, nn}], x], nn + 1], {m, 0, nn/2}], 2 -> 1]

Crossrefs

Cf. A000676.

Sequence in context: A155042 A373638 A001851 * A303963 A304349 A024822

Adjacent sequences: A356372 A356373 A356374 * A356376 A356377 A356378

Keyword

nonn

Author

Geoffrey Critzer, Aug 04 2022

Status

approved